Já tentou iniciar no modo de recuperação (via grub)?
Uma vez no modo de recuperação, você pode fazer:
sudo apt-get update
sudo apt-get upgrade
Como você pode ter pacotes parcialmente instalados, talvez queira executar:
sudo dpkg --configure -a
antes de atualizar e atualizar do grub.