Eu mesmo fiz um caminho muito parecido, eis o que funcionou para mim:
Inicialize no modo de recuperação (tentei versões anteriores até que ele seja inicializado "corretamente") RecoveryMode
Abra um terminal e execute
sudo apt-get install -f
sudo dpkg --configure -a
Se tudo falhar, pode ser bloqueado, então você pode tentar
sudo rm /var/lib/apt/lists/lock
sudo rm /var/cache/apt/archives/lock
cd /var/lib/dpkg/updates
sudo rm *
Então você pode finalmente atualizar tudo e tentar a atualização novamente (eu uso o dist-upgrade para garantir que as dependências sejam resolvidas)
sudo apt-get update
sudo apt-get dist-upgrade