Para resolver esse mesmo problema, eu removi os pacotes do Ubuntu VirtualBox e adicionei linhas ao /etc/apt/sources.list
#Virtualbox
deb http://download.virtualbox.org/virtualbox/debian quantal contrib
Atualize as listagens do apt:
sudo apt-get update
Instale os cabeçalhos para o seu kernel, se eles não estiverem instalados (porque a instalação do VirtualBox precisa deles):
sudo apt-get install linux-headers-$(uname -r)
Instalar o VirtualBox:
sudo apt-get install virtualbox-4.2
Baixe e instale o .deb mais recente para o vagrant e todas as obras.