Se você tem um CD inicializável do Ubuntu, então inicialize a partir do CD, após chroot o seu sistema com falha:
sudo mount /dev/sda1 /mnt
sudo mount --bind /dev /mnt/dev
sudo mount --bind /proc /mnt/proc
sudo mount --bind /sys /mnt/sys
sudo chroot /mnt
Após esse problema, novamente os comandos sudo apt-get update && sudo apt-get upgrade
. Se falhar, execute sudo dpkg-reconfigure -a
. Se terminar, reinicie, remova o CD e tente inicializar normalmente. Espero que ajude.