Eu acho que descobri uma correção.
Meu /etc/environment
tinha a variável CLASSPATH definida para minha instalação anterior do openJDK. Recentemente instalei o Oracle JDK manualmente e removi o openJDK. Mas de alguma forma, /etc/environment
continha o antigo valor de CLASSPATH.
Mas o que me preocupa é que o problema apareceu recentemente que eu poderia instalar / remover pacotes com sucesso mesmo depois da minha reinstalação do java.
Obrigado @gertvdijk pelo seu insight. :)