Não tenho certeza do que estava errado, mas isso finalmente resolveu.
sudo aptitude purge virtinst virt-viewer python-libvirt libvirt0 libvirt-bin
Então eu dei uma volta em /etc/usr/share/var/lib/var/log e limpei tudo relacionado a qemu, kvm, etc.
depois disso, eu apenas reinstalei:
sudo apt-get install qemu-kvm libvirt-bin virtinst bridge-utils
E eu estava pronto para ir.