Eu pessoalmente optaria por uma instalação limpa.
Inicialize em um LiveCD, faça backup dos arquivos da sua casa (que devem estar todos acessíveis ainda) e de quaisquer outros que você queira manter em outra unidade e reinstale. Todo o processo leva cerca de meia hora (dependendo de quantas coisas você tem) e você obtém uma instalação limpa e brilhante.
Você pode tentar recuperar o processo de atualização primeiro, caso seja simples. A partir do LiveCD, abra um terminal e execute:
sudo mount /dev/sdXY /mnt # swap sdXY for your drive/partition
sudo chroot /mnt
apt-get update
apt-get -f dist-upgrade