Consegui fazê-lo esta tarde.
sudo apt-get install --reinstall python python-chardet python-colorama python-distlib python-django python-django-tables2 python-six python-html5lib python-lxml python-minimal python-pkg-resources python-setuptools python-urllib3 python-requests python-pip python-virtualenv
sudo apt-get install --reinstall python-dnspython
sudo apt autoremove
sudo apt-get -f install
Depois de um dia inteiro de aventuras nos picos mais profundos da internet, esses comandos funcionaram para mim.
O python-dnspython e o samba ainda estavam faltando após o primeiro comando, --reinstall python-dnspython
extraiu o samba também. O Autoremove removeu as dependências desnecessárias.