Você precisa reinstalar o gerenciador de atualização. Primeiro, remova / limpe:
sudo apt-get purge update-manager-core update-notifier-common
Em seguida, dê uma olhada na saída do console. Se ele disser que alguns diretórios não puderam ser removidos, exclua-os manualmente. No meu caso:
rm -rf /var/lib/update-manager
rm -rf /var/lib/update-notifier
Se você estiver no 13.04 ou posterior, você também deve fazer isso para limpar as mensagens de atualização em cache:
sudo rm /var/lib/ubuntu-release-upgrader/release-upgrade-available
Em seguida, atualize suas fontes:
sudo apt-get update
Reinstale o gerenciador de atualização:
sudo apt-get install update-manager-core update-notifier-common -y
Apenas se você estiver em um LTS e quiser fazer upgrade para o LTS mais recente, verifique se em /etc/update-manager/release-upgrades
você definiu:
Prompt=lts
Caso contrário (atualizando qualquer versão para uma versão mais recente) defina:
Prompt=normal
Agora o dist-upgrade deve funcionar:
sudo apt-get dist-upgrade