Adding Non Clustered Index to Table Increases Query Results

OK DBA/SQL Server friends, I need your help here with my limited knowledge of SQL Server indexes. Today Devin Knight and I were working on a query for a View. It was taking about a minute to bring back somewhere around 8000 rows so we decided to add a non clustered index to the business key (Personnel Number and Begin Date) of one of the tables. Once we added the non clustered index to the table, the query for our View brought back around 40,000 rows! If we removed the non clustered index, our query once again brought back 8000 rows. What would cause this behavior?

Here's some more background info:

@@version = Microsoft SQL Server 2008 R2 (RTM) - 10.50.1600.1 (X64)   Apr  2 2010 15:48:46   Copyright (c) Microsoft Corporation  Enterprise Edition (64-bit) on Windows NT 6.0 <X64> (Build 6002: Service Pack 2) (Hypervisor)

Table structure: The table in question is a pretty wide table with maybe near 100 columns. There is 1 primary key with a clustered index and there are 3 foreign keys with a non clustered index on one of the foreign key fields. We were adding an additional non clustered index to the two fields that make up the business keys of the table. Both fields that make up the business key are not any of the foreign key fields.

Let me start by saying I haven't run into this - but I'll venture a guess:

I remember reading that in 2008, you could conditionally index tables.  Have you looked at the index definitions on the tables underlying the view to ensure none were created conditionally? 

What I'm thinking in my pea-brain is:

SELECT {whatever}
  FROM TableWithConditionalIndex -- 8,000 rows when the engine picks the conditional index
  
but

SELECT {whatever}
  FROM TableWithNonClusteredIndex_No_Limiters -- all 40,000 rows when the engine picks the non-clustered index without the same limiting conditions

As I said - I haven't run into that - nor have I used the conditional indexing functionality - but is that possible?  Does it work that way?   Now I'm curious and wanting to set it up to try that.

Definitely let us know when you figure this one out - I love a good mystery ( when it's not on my server! ),

Keith

I tweeted it with #sqlhelp last night and a couple guys responded that they thought it could be a bug. The client is running SQL Server 2008 R2 RTM, so I put in a request to installed Cumulative Update 7, so we'll see how that goes.