Hola,
Realmente si es un problema bastante especial.
Es interesante que te ocurrió exactamente ese incoveniente.
Aunque es algo que está en la documentación de como funciona AUTO_INCREMENT en InnoDB.
"An AUTO_INCREMENT column must appear as the first column in an index on an InnoDB table." http://dev.mysql.com/doc/refman/5.1/...-handling.html
Creo que he yo también he aprendido algo nuevo de InnoDB.
Espero haber sido de alguna ayuda.
Saludos,