Tive o mesmo problema, resolvido forçando a atualização do apt e limpando a instalação atual como Andrew sugeriu:
sudo apt-get update
sudo apt-get upgrade
sudo apt-get -f install # (not "install -f"!)
sudo apt-get -y install apt
sudo do-release-upgrade