I just did a new test here. It just compares one green square to another, but you can see plainly what's going on.
URLThe test image has about 256 shades of green in it, going from (0,1.0,0) to (0,0,0). You'd expect the color switched one to have 64 shades of green, but instead only 7 are visible.
It seems from this that the BlitSurface routine picks the first palette entry it finds that's "close enough" to the source color when rendering to a paletted surface.
How to work around this? Well, there was a suggestion made earlier to do the color swapping manually with a pixel-by-pixel brute force routine. This would likely be far slower than the current method but since recoloring is a one-time expense it probably wouldn't be too bad. The thing I don't like about it is that I've had bad experiences with GetPixel and SetPixel in SDL in the past.