A: 

IIRC GIF's are limited to a specific pallete on .NET. There are workarounds, but they were above my understanding.

leppie
+2  A: 

GIF files are limited to 256 colors as far as I know, so it resorts to dithering. PNG is probably the format you need.

Or you can look here for a solution using a complex quantizer to build a custom palette (I don't take responsibility for the code in the link, never tried myself).

This other link from Microsoft has an in-depth analysis of the problem.

Hope this helps.

Marco M.
See my update to the original question. This answer eventually pointed me to the solution.
JeffK