Ubuntu's package is currently even more fucked than it used to be.
is it possible to get them to fix their package?!?!?!?
i notice that the text you posted has "amd64" are you running pure64bit OS
i think when i first changed to 64bit the 1.1.0 installer didn't work and i had to manually extract the files and install the game manually
to manually extract the files do
./tremulous-1.1.0-installer.x86.run --target tremulous
then you want to login as root use su or something and copy the files and set permissions
cp -R ./tremulous /usr/local/games
cd /usr/local/games/tremulous
chown -R root:root ./
chmod -R 755 ./
make sure when you run it you use /usr/local/games/tremulous as your working directory and i recommend upgrading to a newer client after you install it
i think that's all correct im sure someone will correct me if im wrong by the time you read it anyway good luck