Yeah, I'll explain this in detail:
In NSE you know how in advance mode you have the "Pal Registers"?
This has to be changed to reflect the palette change.
NSE does it for you on all of the default palettes, but for custom palettes NSE is unable to evaluate the proper bytes (I just never coded it... :knockedou)
Here's how to do it yourself:
The important part of the pal register is the first two bytes (the the first 4 letters/numbers).
First Byte:
For regular sized sprites (between the 16x16 and 56 x 56 pixels sizes, I think) it's the palette index + 0xF;
For larger sprites (Like the boats in Firered) it's the palette index + 0x6;
For small sprites (Like the pokeball) it's the palette index + 0x3F;
Second Byte:
The second byte is usually (not in the case of some):
0x1 for animated sprites and 0x0 for non-animated sprites.
So for a person sprite that uses palette 0x22 the Pal Registers would be 31010000
Note: You can change the Pal Register in NSE's Hex-Editor (View->Hex Select "Sprite-Offset" from the drop down)
Hope this works. If you need anymore help ask me.
P.S. don't forget to credit me for dis :P