Wenn du die Farben mit Paint von 16 Mio. Farben auf 256 umwandelst,
werden die Farben fast immer schlecht verfälscht. Du solltest es
mit einem anderen Tool versuchen, z.B. Irfan View umwandeln.

http://www.alles-freeware.de/files/irfan/iview385.exe

Der Irfan View gleicht die Farben beim Umwandeln in etwa aus,
dann sollte es keine Probleme mehr geben.