un gif vectorizado??? dificil lo tienes.
Cuando pasas en photoshop una imagen de 300 a 72 es nomal que empeore pues le estar reduciendo la resolucion de la imagen.
Supongo que lo estas haciendo para la web. porlo que la resolucion sera de 72 con el tamaño en pixeles que debe tener, pues el explorador no hara mucho mas.
Asi que si es un dibujo muy errebesado, no conseguiras que se vea igual que cuando lo tienes en un programa de vectores como corel o illustrator.
Si es para la web una solucion es que lo pases en flash, (si es transparente igualando los fondos). pues flash si que muestra vectores.
S