Il formato .gif non possiede la proprietà di sfumare sino alla trasparenza. Il pixel o è pieno, o è vuoto. In rete trovi tutte le spiegazioni. La prima che ho trovato:
http://forum.html.it/forum/showthread/t-1358417.html
Visualizzando la tua immagine, mi sono accorto casualmente che assorbe molta CPU: probabilmente è "sovraccarica/troppo grande".
Lavoro raramente con le gif, sopratutto animate, ma posso dirti che PS non è il massimo per questo formato. Anche nella generazione delle trasparenze, spesso mi son trovato a ritoccare i pixel "a mano", per correggere sporcizie.
Se hai possibilità, ti consiglio di usare Fireworks (non conosco), che nasce proprio a questo scopo.