Is there anything more to it than deleting the /usr/local/games/tremulous directory and deleting the /usr/local/bin/tremulous symlink on a debian system?
FYI, there's an uninstall script in the /usr/local/games/tremulous directory that takes of this. It uses the info stored in your home's .loki directory...