it looks like whatever you are creating it in, is using a >256 colour palette and then dithering it, or its dithering during the same, which seems less likely given the first image and the number of colours in the 2nd image vs the 1rst.
make sure you are editing in 256 colours in the first place, pro motion
http://www.cosmigo.com is an excellent palettized image editor
or as lord h said use a web based palette, usually making sure you use less than 250 colours in your palette will make it render ok., its possible the browser itself is dithering it using its own palette.
if you are using photoshop beware as it has some tricks for low colour images that it applies when you load, so you don't always see the effects after its saved.