Acabamos de encontrar uma solução:
sudo apt-get install $(dpkg --get-selections | awk '{print $1}' | egrep -v 'dpkg|apt|mysql|mythtv')
sudo apt-get update
sudo apt-get install $(dpkg --get-selections | awk '{print $1}' | egrep -v 'dpkg|apt|mysql|mythtv')
Agora, pegue a lista de itens que falharam na instalação e, em seguida, coloque-a no final do próximo comando:
sudo apt-get remove --purge <add packages in previous item>
fakeroot -u dpkg-repack $(dpkg --get-selections | grep install | cut -f1)