Você já tentou?
$ sudo apt-get check
Se você tiver alguns problemas de biblioteca, esse comando dirá a você. Nesse caso, você pode resolvê-lo usando:
$ sudo apt-get -f install
Isso consertará dependências quebradas, isso pode ser o problema.