MySql може да игнорира индекс, ако индексът има достъп до повече от 30% от редовете на таблицата. Можете да опитате FORCE INDEX [име_индекс], той ще използва индекс във всеки случай.
Стойността на sysvar_max_seeks_for_key също влияе върху това дали индексът се използва или не:
-
http://dev.mysql.com /doc/refman/5.0/en/server-system-variables.html#sysvar_max_seeks_for_key
Опитайте да промените тази стойност на по-малко число.
Търсете подобни заявки в SO.