Eu tinha instalado através do seguinte comando:
sudo apt-get install qemu-kvm libvirt-bin ubuntu-vm-builder bridge-utils
Por isso, meu comando de desinstalação era:
sudo apt-get remove --purge qemu-kvm libvirt-bin ubuntu-vm-builder bridge-utils
Que funcionou bem para mim.