Wie Ninty schon gesagt hat liegt es ziemlich sicher an der Farbtiefe, doch diese zu ändern geht noch einfacher als ninty's Methode. Wie du gesagt hast, benuzt du ja Photoshop klicke auf Bild > Modus > Indizierte farben schon ist das Bild auf eine Ebene reduziert und im 8-Bit modus.