Tente primeiro:
sudo rm /var/lib/dpkg/available
sudo touch /var/lib/dpkg/available
sudo sh -c 'for i in /var/lib/apt/lists/*_Packages; do dpkg --merge-avail "$i"; done'
Perigoso, se a instrução anterior não resolver o problema ...
sudo dpkg --configure -a
sudo apt-get -f install
sudo apt-get clean
sudo apt-get update && sudo apt-get upgrade
Por último, pode haver uma grande carga de tráfego.