Parece que o banco de dados está danificado. Você pode tentar restaurá-lo de um estado anterior , assim:
sudo sh -c 'zcat /var/backups/dpkg.status.1.gz > /var/lib/dpkg/status'
Certifique-se de copiar o arquivo primeiro para outro backup.
Editar:
su
zcat /var/backups/dpkg.status.1.gz > /var/lib/dpkg/status
exit