La paleta no te cambia porque la paleta que te proporciona NSE no es la correcta.
Els backsprite tiene otra paleta aparte, esta en este offset E76EC1 en FireRed claro, en Ruby se debería cambiar sin problemas.
El back yo lo cambio con NSE y bien, solo inserta la imagen luego la paleta la insertas en el offset que te deje y listo.