O MySQL não usará o índice se estimar que selecionaria uma porção significativamente grande da tabela e achar que uma varredura de tabela é realmente mais eficiente nesses casos.
Por analogia, esta é a razão pela qual o índice de um livro não contém palavras muito comuns como "o" -- porque seria uma perda de tempo procurar a palavra no índice e descobrir que a lista de números de página é uma lista muito longa, até mesmo todas as páginas do livro. Seria mais eficiente simplesmente ler o livro de capa a capa.
Minha experiência é que isso acontece no MySQL se os critérios de pesquisa de uma consulta corresponderem a mais de 20% da tabela, e isso geralmente é o ponto de cruzamento correto. Pode haver alguma variação com base nos tipos de dados, tamanho da tabela, etc.
Você pode dar uma dica ao MySQL para convencê-lo de que uma varredura de tabela seria proibitivamente cara, então seria muito mais provável usar o índice. Isso geralmente não é necessário, mas você pode fazer assim:
SELECT taskid FROM tasktransitions FORCE INDEX (transitiondate_ix)
WHERE transitiondate>'2013-09-31 00:00:00';
