Es un problema de dependencias.
Cuando existen relaciones de FK, es mejor hacerlo en más de un paso.
Manual de referencia:
Cita: Si usa un comando DELETE de varias tablas incluyendo tablas InnoDB para las que hay restricciones de clave foránea, el optimizador MySQL puede procesar tablas en un orden ditinto del de su relación padre/hijo. En este caso, el comando falla y se deshace. En su lugar, debe borrar de una tabla úncia y confiar en la capacidad de ON DELETE que proporciona InnoDB para hacer que las otras tablas se modifiquen correctamente.
http://dev.mysql.com/doc/refman/5.0/es/delete.html