Mmm... non è che la gif è salvata a 256 colori?
Magari quello che sto per dire è dato per scontato ed il problema è un altro, ma non si sa mai...
Salva l'immagine in formato bmp, poi salvala a 24 bit (banalmente anche con il paint di Windows), poi aprila con Photoshop (o il sw che utilizzi normalmente...) ridimensionala e salvala nuovamente come gif...


Ciao,
Fede