Estava com o mesmo problema, sendo instalando tomcat 6.0 pelo Synaptc ou apt-get.
A solução que eu encontrei foi baixar o tomcat 6.0 - Core (http://tomcat.apache.org/download-60.cgi),
apenas descompactei o tomcat 6.0 não é necessário "instalar" e depois ao tentar configurar o server pelo eclipse e deu tudo certo.
