Encontrou uma resposta em outra pergunta:
O dpkg faz um backup regular do status completo do pacote do sistema para /var/backups/dpkg.status.*.gz. Se você achar que o status do seu pacote está fora de sincronia com os pacotes reais instalados, poderá substituir o arquivo de status em /var/lib/dpkg/status
pelo arquivo de status contido no backup. Execute os seguintes comandos como sudo:
cp /var/lib/dpkg/status /var/lib/dpkg/status.bak
cp /var/backups/dpkg.status.*.gz /var/lib/dpkg/
gunzip -d /var/lib/dpkg/dpkg.status.*.gz
mv /var/lib/dpkg/dpkg.status.* /var/lib/dpkg/status
Agora você deve conseguir fazer um apt-get update && apt-get upgrade
para atualizar para os pacotes mais recentes.