Hola dalfeju!
No se que PS estás usando pero para las últimas versiones esto está prácticamente solucionado.
El tema de los fondos y degradados en Gif siempre ha sido ese que planteas.
Una sugerencia que te hago es la de utilizar siempre la herramienta de Optimizar para Web de PS,
es la mejor forma no solo de optimizar para hacer la red más navegable y rápida sino la de "ver" realmente lo que te está quedando.
Chequea que no tengas activada la función "Restrictiva" de guardado GIF, es por lo único q e sale así, mientras está en las otras no tiene que "romperse" el degradado.
En ambas formas, pasando por Optimizar o por guardado directo justamente si activas las funciones "para Web" te saldrá toda rota también.
He hecho esta prueba y como ves no tiene que dar problemas.
[URL=http://img510.imageshack.us/i/degradez.gif/][IMG]http://img510.imageshack.us/img510/5226/degradez.gif[/IMG][/URL]
Espero haber ayudado en algo.
Slds, E