Help with overworld sprite palettes!

That looks correct. Do you mean the first time you meet Shadow in the South Figaro Pub? He is loaded as an NPC on that map so for that you'd need to change his palette using the level editor utility. There are many instances of characters and NPCs being used as such that will require changing them with the level editor. Their overworld palette is loaded and used once you have acquired them into your party and can control them in the lead spot.