Also, keep in mind that SQL Server stores statistics for left-based subsets of an index. You may want to look at all SPs or queries which refer to the table in question and redesign indexes.

Read more about that here - http://sqlinthewild.co.za/index.php/2009/01/19/index-columns-selectivity-and-equality-predicates/