Sadly, jpg compression adds a lot of artifacts and distortion in detailed areas, therefore more shading and colour-palette information too.
If you stick with uncompressed images like bmp, gif, tif or tga (some of these get real large), you'll find it easier to work with.
If you look at your avatar image, there's only about 10-11 unique colours used, all flat-even shades, so there's no reason to need anymore than say a 256 colour palette.
hope it helps.
MM.