This is probably the correct behavior. I've not bumped into a lot of situations where the query optimizer selects a bad plan.

Update your index statistics. The query optimizer uses the statistics to determine how useful an index is.

Also, if SQL Server determines that it will be returning more than 12 to 15% of the table, it will perform a table scan.

Can you post the query and DDL? Is this query in a stored procedure? If it is, the rules change.

I'd also suggest that you purchase "Inside SQL Server 2000."

- Mike