I agree whole heartedly but I couldn't get the artifacts to go away. There were way too many colors when I did it gradient like (over 1000) If you guys can modify it to look better go on a head I don't mind.
The non-image messed up one looks like this

which is much nicer

I wrote this program to try and help me out with it (you'll need .net framework for the program to run)
http://www.themikausprojects.com/neoflash/imagePaletteFix.exeIt takes an image tells you how many unique colors there are and then you can set tolerances on it. You can say anything that is withing 25 on the red 30 on the blue and 27 on the green of this color IS this color and then you can save the image with the swapped colors.
I don't have directions on how to use it, but double clicks are your friend and maybe if someone is interested I'll make a short text or something, but for now if you guys want to fiddle you can.
-EDIT-
Directions :
Click "Load Image" Find the image you want to use and load it.
This will populate one of the boxes with colors and extend its scrollbar (these are the colors in the image and you can move the scroll bar to change the color)
Next to this color box is description of the selected color (R,G,B) double click this box to select it in the filters section. Click the box next to the filters section to bring up a color chooser. This is used just to assign the tolerance values for the R,G,B if you select a color with 25,25,25 then it'll be your color.R + 25, color.G + 25... etc.
Click "Add Filter"
then click "Refilter Image" (this may take some time) but it should tell you how many colors there are now in the image after the filter is applied.
If you want to see what it looks like click the preview image button and if you like what you see you can click "Save Image" (but you'll need to save it as a different name than the original image or it'll crash)
You can add more than one filter at a time. And sometimes the program acts funny.