Tente em um console "aptitude search jdk" e observe os resultados.
Você pode identificar um personagem à esquerda de cada linha. Se esse caractere for um 'i', significa que o pacote está atualmente instalado no sistema. Provavelmente será algo como "sun-java6-jdk" ou "openjdk-6-jdk".
Nesse ponto, você pode fazer "sudo aptitude purge $ 1", em que $ 1 é o nome do pacote que você encontrou na lista de resultados anterior.