Abra um terminal pressionando Ctrl + Alt + T e digite os seguintes comandos um por um:
sudo dpkg --configure -a
sudo aptitude update
sudo aptitude upgrade
Se isso não resolver seu problema, use os seguintes comandos:
sudo rm -rvf /var/lib/apt/lists/*
sudo apt-get update