Eu tive exatamente o mesmo problema.
Eu tive que executar este comando (veja abaixo) para ver o que todas as bibliotecas relacionadas ao tomcat estão lá e remover TODAS as bibliotecas relacionadas ao tomcat:
Para ver o que todas as bibliotecas relacionadas ao tomcat estão lá:
dpkg -l | grep -i tomcat
Para remover uma biblioteca de tomcat:
dpkg -P <library-name>
Então, eu reinstalei o tomcat7 usando o comando:
sudo apt-get install tomcat7
[Durante a instalação, ele cita mensagens dizendo que vai instalar algumas das outras bibliotecas relacionadas ao tomcat7 - eu escolhi - yes].
Ele instalou o tomcat7 e o iniciou.
Então, parei e reiniciei o tomcat7 usando estes comandos:
/etc/init.d/tomcat7 stop
/etc/init.d/tomcat7 start