Palette Editing Tutorial (outdated)

those particular palettes are technically NPC versions of the characters (at least how the game reads it) you need to edit those via the level editor, when controlling them though they should be assigned the palette you assigned them

I would add to that that you need to change them on every map the character (as an NPC) appear, because even if it's the same character, it's a different NPC.