Eu tive o mesmo problema com o meu login e quando olhei para ele vi que o dpkg estava corrompido - depois de tentar os passos deste artigo eu tive melhor sorte: link
Eu tive que realmente apagar a linha ofensiva em / var / lib / dpkg / status que impedia que o dpkg atualizasse qualquer pacote, mas depois disso essas etapas funcionaram para me colocar de volta em 12.04.
sudo cp /var/lib/dpkg/status-old /var/lib/dpkg/status
sudo aptitude update
sudo aptitude full-upgrade
Em seguida, certifique-se de reiniciar.
Espero que isso ajude você também