É porque, o pacote unistall necessário foi encontrado no arquivo de status do diretório dpkg. Você pode superar o erro como abaixo.
#cd /var/lib/dpkg/
#status status.orig
# vim status
Procure por um bloco como esse:
% bl0ck_qu0te%Aqui, você deve excluir apenas o bloco icedtea-netx: amd64. Isso significa começar com o pacote: icedtea-netx: amd64 e até o outro bloco de pacote. Depois de deletar o bloco tente removê-lo novamente, ele funcionará.