Para quem tem este problema - o problema está relacionado com os meus controladores NVidia - isto resolveu o problema:
NOTA: Não seja burro como eu. Eu fiquei tipo "Ah, vou desativá-los através do gerenciador de software da GUI e voltar aos drivers Nouveau temporariamente!"
Como o DPKG não consegue instalar os pacotes - sua máquina nunca desabilitará os drivers da NVidia e se você reiniciar, você receberá um problema no modo de recuperação - reparar o DPKG (é só selecionar o dpkg a opção e ele vai fazer isso automaticamente - assim como instalar os aplicativos pendurados)
ENTÃO - reative os drivers NVidia assim que você inicializar de volta no sistema operacional e reinicializar.
TL; DR: Desativa a placa NVidia apenas através do centro de controle da NVidia.