Solucionado !
Para todo el que tenga problemas que use este tutorial. Tras mucho investigar he dado con la solucion, y es mejor hacer justo lo que dice el tutorial.

http://wahackforo.com/t-buscar-direcciones-de-las-paletas-con-ape

Ya que no daba con la direccion HEX del sprite de la heroina (o de cualquier sprite) con ese tutorial aprendi a buscar la paleta del sprite y que el mismo APE me diera la direccion HEX del sprite al que le quiero cambiar la paleta. Luego solo tuve que cambiar las paletas y listo ya va todo genial !

Gracias a todos :D