Entra no Synaptic, escolhe o filtro por estado, clica no botão "Estado" (ou "Status"), depois no item "Instalado"; procura por "icedtea" na caixa lá em cima, vai ter um monte de pacotes com esse nome no sistema.
Feito isso, marca todos e manda fazer remoção completa. Pode remover os pacotes "default-jre" à vontade, se o objetivo é usar o Oracle JAVA.