Hmm, normalerweise ist Photoshop ein gutes Programm, um Farben zu indizieren.

Wie komprimierst du denn mit Photoshop?
Versuchs mal so:
Datei/Für Web Speichern

PNG 8 auswählen und abspeichern.

Ich machs immer so und habe gute Ergebnisse.