Cain's palette-hack went a lot better. Have you thought about upgrading the field sprites from 16×16 to 16×24? I wouldn't be able to draw new sprites, unfortunately, but it'd be neat.
EDIT: I used the PSP battle sprites to recolour Paladin Cecil, which came out looking pretty good.
EDIT 2: I thought about doing Cid, too, but he ends up looking like a silver bullet. I don't know why the PSP version didn't use the DS version's portrait colours—Cid's portrait there actually fits the sprites.
EDIT 3: Child Lydia, hair and hair-piece from portrait, clothing brightened from PSP battle sprites to counteract the 'dulling' of her hair.
EDIT 4: And here's adult Lydia. If it's possible, I'd prefer to have the summon-sprite use a different palette from the rest to preserve the yellow glow.
EDIT 5: You get a palette-squish, and you get a palette-squish...everybody gets a palette-squish! (All four spritesheets are now 16-colour. May take some work to free up a colour for three of 'em for transparency, though.)
EDIT 6: Redid DK Cecil.