MySQL no usará el índice si estima que seleccionaría una porción significativamente grande de la tabla y cree que un escaneo de tabla es realmente más eficiente en esos casos.
Por analogía, esta es la razón por la que el índice de un libro no contiene palabras muy comunes como "el", porque sería una pérdida de tiempo buscar la palabra en el índice y encontrar que la lista de números de página es una lista muy larga, incluso cada página del libro. Sería más eficiente simplemente leer el libro de principio a fin.
Mi experiencia es que esto sucede en MySQL si los criterios de búsqueda de una consulta coinciden con más del 20% de la tabla, y este suele ser el punto de cruce correcto. Podría haber alguna variación según los tipos de datos, el tamaño de la tabla, etc.
Puede darle una pista a MySQL para convencerlo de que un escaneo de tabla sería prohibitivamente costoso, por lo que sería mucho más probable que use el índice. Esto no suele ser necesario, pero puedes hacerlo así:
SELECT taskid FROM tasktransitions FORCE INDEX (transitiondate_ix)
WHERE transitiondate>'2013-09-31 00:00:00';
