Tente abrir um terminal e execute os seguintes comandos:
sudo apt-get update
sudo apt-get -f install
Eu vejo esse tipo de problema com mais freqüência quando meus bancos de dados apt estão apontando para versões mais antigas de arquivos de pacotes que foram removidos, portanto, não podem mais ser baixados.
Se essa não for a solução, o apt-get -f
fornecerá mais resultados que apontem para a causa do problema.