Si vas a insertar sprites, inserta las nuevas paletas con el editor de sprites que los vayas a insertar. (Unlz, nse..etc)
Si no, si cambias las viejas paletas direcamente a ojo, te pasara lo que te ha pasado.
Que los colores estan desordenados, dado que cada imagen indexada guarda la informacion de los colores en una posicion u otra.
Photoshop/charadter maker pro nose que criterio siguen para el orden de los colores, en cambio nintendo si y es que acostumhra a colocar el color blanco y negro en la 15 y 16 posicion).