Eu consegui resolver isso muito cruamente. Renomei /etc/init.d/vboxdrv
para vboxdrv.bak
para que o serviço de módulo do kernel do Virtualbox não fosse iniciado (e, portanto, não ficasse preso durante a interrupção).
Eu reiniciei e fiz um sudo apt-get remove --purge virtualbox-4.1
, que funcionou bem.
Tenho certeza de que há uma maneira mais elegante de fazer isso, e ficarei feliz se alguém sugerir isso, mas estou feliz que isso funcionou para mim, já que eu precisava urgentemente que meu PC estivesse funcionando.
EDIT: O problema parece ser devido à atualização do kernel - eu tentei 3.3rc6 com 11.10 e 3.3rc7 com 12.04 e ambos causaram os problemas que descrevi com o Virtualbox e VMWare.
No entanto Virtualbox funciona muito bem em versões estáveis do kernel - Eu estou atualmente em 3.2.0-18 no Ubuntu 12.04 (eu não tentei VMWare, mas suponho que o problema com isso será resolvido também)