Eu tive exatamente o mesmo problema com o Ubuntu e minha experiência foi que era principalmente a Unity tornando as coisas terrivelmente lentas. Mude de Unity para Gnome, LXDE ou algum outro gerenciador de janelas leve e acredito que as coisas ficarão melhores instantaneamente.
Além disso, minha experiência é que qualquer VM deve receber pelo menos dois núcleos, se possível, pois isso também melhorará o desempenho. 36 MB ou mais de RAM da placa de vídeo devem ser alocados para a máquina virtual, pois isso permite a integração total entre o host e a tela de VMs.