Depois de tentar
sudo dpkg --configure -a
e
sudo apt-get install -f
o problema de um pacote quebrado ainda existe, a solução é editar o arquivo dpkg status manualmente.
'sudo nano /var/lib/dpkg/status' (you can use vi or gedit instead of nano)
Localize o pacote corrompido e remova todo o bloco de informações sobre ele e salve o arquivo.