2 similar queries in large sql server table - 1 takes too long
The explain plan (or execution plan) should tell you exactly where the difference lies, and which indexes are being used.

See here for more info on how to get an explain plan.