Am I correct when I say you want to use a 256 color pallette so you can use the same sprites but with a different color set?

If so, do you have any alternative ideas for this problem?