Se você estava recebendo este erro em uma operação install , uma causa provável seria que o banco de dados local de pacotes disponíveis não correspondesse ao que está disponível no servidor, portanto, o APT está solicitando versões do pacote não existem mais. A correção nesse caso é executar apt-get update para atualizar o banco de dados de disponibilidade local. No entanto, não vejo como isso pode acontecer em uma operação de remoção ou remoção.
É possível que o banco de dados do APT estivesse em um estado de transição com dependências não resolvidas. O APT não pode lidar com dependências não resolvidas, então a primeira coisa que precisa fazer, mesmo em uma operação de remoção, é consertar essas dependências. Tente executar apt-get -f install para entrar em um estado consistente sem alterar o que o APT considera como sendo o estado desejado, antes de fazer alterações no estado desejado, como solicitar a instalação ou a remoção de um pacote.