No que diz respeito ao ouvinte ainda na porta 8080, você vai querer verificar se não há um conector definido para essa porta e se nenhuma outra instância do tomcat está em execução.
É provável que a causa do problema com a porta 80 seja que as portas baixas exigem privilégios de root para serem vinculadas, e o tomcat, por padrão, é executado como um usuário não raiz. A maneira de contornar isso é usar o authbind.
apt-get install authbind
touch /etc/authbind/byport/80
chown tomcat6:tomcat6 /etc/authbind/byport/80
Em seguida, modifique o arquivo de configuração do tomcat para ativar o suporte a authbind.
nano /etc/default/tomcat6
Acredito que a configuração do authbind esteja próxima da parte inferior do arquivo.