SQLSever Not Using Index

Hello,

We are having a very strange problem. We have a table with about 5
million rows in it. The problem is with one of the non clustered
indexes. I have noticed that sometimes in query analyzer, when doing
an execution plan, the optimizer is NOT doing an index seek, or a
bookmark lookup when the query should. It sometimes will do a full
clustered index scan on the primary key, which takes much longer. For
example:

select * from MyTable where fk_value = 1001201

the optimizer WILL NOT do an index seek or bookmark lookup and for this
query:

select * from MyTable where fk_value = 1001222

it WILL do an index seek on the non clustered index. The only
difference is the values specified for fk_value.

I have done a update statistics MyTable with full scan and it still
will not use the non clustered index for some queries. I have also
tried:

select * from MyTable (INDEX=IX_FK_VALUE) where fk_value = 1001201

to force the optimizer to use this index, but it still DOES NOT use
this index. Its wierd because for some values it will use the index,
and some it will not. Not sure what is going on

Any help would be greatly appreciated.

TIA