Lo que pasa, es que en rubí, los trainers, cuando pasas de un lado a otro, no llevan consigo mismo su paleta.
Si no que has de buscarla en el unlz.
La mejor manera de guiarte, es desde el principio, es decir...
El primer sprite del unlz gba es la chica con falda.
(El numero 1292 y su paleta correspondiente es la 1039)
Si por ejemplo, quieres cambiar la paleta del sprite del protagonista, habrás de hacer los siguiente.
Detectar que numero es el sprite (1294), seguido de eso, hacemos una resta.
El sprite actual que queremos cambiar (1294) menos el primer sprite que encontramos. (1292).
Es decir

1294 - 1292 = 2

Y el numero obtenido, será el numero de veces, que habremos de darle a "next pallete" hasta que encontremos LA PALETA EXACTA, del sprite a cambiar.
Una vez encontrado, ya importas el sprite que quieras insertar, y su paleta tambien, write to rom y listo!!

PD: Por si te interesa, la paleta del protagonista es la 1041.