I'm going to assume that you're saving for web, seeing as it's a GIF.

Try fiddling with the Dither settings on the right side of the 'save for web' dialog - A word of warning though: when messing around with the colour and dither settings of GIF files, the filesize gets pushed up DRAMATICALLY, so there will always have to be a balance between quality and filesize/animation speed...