I already tried the smooth/crisp/sharp/etc. On a new document, it works, but since the pic started as a gif file, it won't work. The pixelating that you see is with the antialiasing on smooth. I even went so far as to create the text in a new doc so it would be smooth, then cut and paste it into the main graphic. Again, in the new one, nice smooth edges, but as soon as I paste it into the header - pixelation.
I'm hoping to have a better copy of the pic (either a psd or a higher resolution) later today. Hopefully that will help with the pixelation.