Instead of modifying the original image through the image manipulation program of your choice, you can edit the palette of the image separately and then load the edited palette into the original image. I recommend using Palette Suite as it is good for editing a range of colors and making gradients. Palette Suite also allows you to load a palette into an image through the Use Palette tab.