A ordem do índice é importante quando suas condições de consulta se aplicam apenas a PART do índice. Considerar:

1. 
   SELECT * FROM table WHERE first_name="john" AND last_name="doe"
   
2. 
   SELECT * FROM table WHERE first_name="john"
   
3. 
   SELECT * FROM table WHERE last_name="doe"
   

Se o seu índice for (first_name , last_name ) as consultas 1 e 2 irão usá-lo, a consulta nº 3 não.Se seu índice for (last_name , first_name ) as consultas 1 e 3 irão usá-lo, a consulta #2 não. Alterar a ordem de condição na cláusula WHERE não tem efeito em nenhum dos casos.

Os detalhes estão aqui

Atualizar :
Caso o acima não esteja claro - o MySQL só pode usar um índice se as colunas nas condições de consulta formarem um prefixo mais à esquerda do índice. A consulta #2 acima não pode usar (last_name , first_name ) porque é baseado apenas em first_name e first_name NÃO é o prefixo mais à esquerda do (last_name , first_name ) índice.

A ordem das condições DENTRO da consulta não importa; a consulta nº 1 acima poderá usar (last_name , first_name ) indexa muito bem porque suas condições são first_name e last_name e, juntos, eles formam um prefixo mais à esquerda de (last_name , first_name ) índice.