This definitely works out then.
It all depends on how many colors each character uses. The main characters (Guy, Haggar, Cody) will be the ones you look at the most so they should look fab all the time and probably have more colors than the baddies. Baddies perhaps can be sorted out with 4 colors. If you set 3 4 color palettes that's 12, plus the 6 from the main charachter is 18. That leaves you with 14 colors for the stage!! Even if you had 10 colors on teh stage it could work out (and you can have one extra baddie palette)
As said before, it's all in the reworking. Currently I don't have time to help out on the gfx rework, if my schedule frees up and you guys are still working on stuff, I'll give it a go. I used to love that (converted gfx to limited shit like NGPC).