Faça o mesmo que na outra pergunta ( Gerenciador de pacotes com falha? ):
sudo apt-get update
sudo apt-get clean
sudo apt-get autoremove
sudo apt-get update && sudo apt-get upgrade
sudo dpkg --configure -a
sudo apt-get install -f
Edit: oops, desculpe, você já fez isso. Eu recomendo pular o dpkg --configure -a
e primeiro fazer apt-get install -f
.