I think there's a problem on your end. When you create a graphic, it has the default extension of .psp and, unless you have changed it, will have 16+ million colors available. To save as a .GIF, you have to reduce the amount of colors to 256 (or less). Obviously, if your image was created using a 16 million color pallet and you change to a 256 color pallet, your going to get some color change.
The only time I use a GIF is when I need a transparent background.
There's always a better way. The fun is trying to find it!