eu usei
dpkg --remove --force-remove sun-java6-bin
O problema foi causado por uma instalação incompleta do JDK6
Para qualquer um que tenha esse problema, recomendo instalar o Gerenciador de Pacotes Synaptic após corrigir isso para evitar problemas como esse no futuro.