Ah, ese problema sí que lo he visto varias veces. Yo apostaría a que no has indexado correctamente la paleta. ¿Recuerdas haberle dado al "Colors 15-bit" o algo similar en el CMP?
Y luego al insertar tu tile, ¿usaste la versión que habías guardado luego de indexar la paleta? (paso anterior) ¿O usaste la original?