En última instancia, la respuesta aceptada anterior es correcta.
La ayuda de @RandomSeed me hizo pensar en la dirección correcta. Básicamente, los planes de optimización creados en 5.6 son significativamente diferentes de los de 5.5, por lo que probablemente tendrá que volver a trabajar en su consulta, como lo hice yo.
No terminé usando el FORCE INDEX , pero en su lugar eliminé partes de la consulta hasta que determiné qué estaba causando que 5.6 no viera el índice. Luego modifiqué la lógica de la aplicación para solucionarlo.
