Isso aconteceu comigo uma vez antes.
Você vai querer usar o seu Live Disc e inicializar nele. A partir daqui, chroot em sua partição com a instalação quebrada. (Se você não sabe como chroot, vá em frente e me pergunte em um comentário: eu ficarei mais do que feliz em ajudar.)
Em seguida, você deseja executar os seguintes comandos no terminal:
sudo dpkg --configure -a
sudo apt-get update
sudo apt-get upgrade
Se isso não ajudar, me avise.
E, para referência: você estava atualizando a versão ou apenas uma atualização geral de software?