O erro original também fornece a solução:
You might want to run 'apt-get -f install' to correct these.
Se você não viu isso antes, você precisa executar exatamente esse comando. Fazendo o contrário, você começa:
Try 'apt-get -f install' with no packages (or specify a solution).
Isso geralmente corrige o problema.