Tenta estes seguintes comandos, no terminal (Ctrl + Alt + T):
sudo rm -r /var/lib/apt/lists/* -vf ; sudo apt-get autoclean ; sudo apt-get autoremove --purge ; sudo apt-get update ; sudo apt-get upgrade ; sudo apt-get safe-upgrade
E depois
sudo rm /var/lib/apt/lists/* -vf
sudo apt-get update
Se não funcionar, tente este outro:
sudo apt-get -f install