Setz das Bild, bevor du es verkleinerst auf 256 Farben runter. So ist die Farbpalette festgelegt und es sollte nichtmehr diese Übergänge geben.