One approach that might help would be to specify the (few) columns you actually need instead of just using the "blanket" SELECT *.....
When you define a small set of columns to retrieve, you might be able to create a covering index (a nonclustered index that contains all the columns you need) that could be used to satisfy the query, and thus possibly avoid an index scan.
When using SELECT * ... you're more or less making sure you cannot make good use of any of the indices - since in the end, the fact you want ALL the data will always have to go back to the actual data pages (the clustered index leaf level pages) and thus more often than not, the query optimizer will just "give up" and switch to a clustered index scan.