Try if it is gnome that slows down the stuff.
Try to desactivate X/gdm (run as root: /etc/init.d/gdm stop) and then login on text-console, type in
X
(wait for X to start, switch back to tty and then)
xterm -display :0 &
Now you should have an X-Server with a plain xterm open. In that xterm, simply type
/usr/games/tremulous
and then watch. If it runs fast now, gnome consumes too many ressources.