Behdad, what is most likely going on is that your X server is running software fallbacks to draw the antialiased glyphs.

To draw one pixel of an antialiased glyph, the X server has to (a) read the existing pixel, (b) blend that pixel with the alpha value for the glyph pixel, then (c) write the result back to the screen. The killer is (a). Reading pixels out of video memory is really, really, really slow. Perversely enough, the better video card you have, the more likely it is that it has lots of memory, and the worse performance you get.

Try running the antialiased test again with

     XAANoOffscreenPixmaps       False

in your xorg.conf file. This will cause gnome-terminal to draw to system memory which is much faster for antialiasing. Unfortuntately it will also cause other stuff such as painting the background to become slower.