Após a tentativa de utilizar o VirtualBox em um dedicado OVH tive o problema em iniciar as VMs, este problema ocorre graças aos servidores da OVH possuem um kernel próprio dificultando a compilação do driver do Virtualbox, para resolver este problema vamos trocar o kernel.

Instalem o VirtualBox, e após a instalação recomendo subir o acesso RDP, vocês podem ver como neste post.

Agora para rodar o virtualbox é necessário trocar de kernel, antes disso é necessário saber qual o kernel atual do sistema

uname -r

Após isto vamos instalar uma nova imagem do kernel

apt-get install linux-image-server

Vamos a pasta do Grub2 e listar o diretório.

cd /etc/grub.d/
ls

Podemos ver os sistemas que estão no boot do Grub, agora vamos retirar o kernel da OVH do boot

mv 06_OVHkernel /root/

Atualizamos o grub

update-grub

Reinicie o seu sistema

sudo init 6

Vamos verificar qual o kernel ativo agora:

uname -r

Como podemos ver já estamos com o kernel novo.

Agora vamos instalar o novo cabeçalho do kernel o qual o virtualbox utiliza para compilar seus drivers.

apt-get install linux-headers-`uname -r`

Após isto execute o comando para compilar os drives do virtualbox, e instalar o dkms.

sudo apt-get install dkms
sudo /etc/init.d/vboxdrv setup

Agora já deve conseguir subir suas vms normalmente.

Vale lembrar que este é sempre bom fazer backup antes de fazer alterações em kernel, faça por sua conta em risco, aqui funcionou as duas vezes que precisei. :)

Enjoy.

Fonte: http://wiki.artica.fr/index.php/VirtualBox:_Unable_to_start_Virtual_Machines_on_OVH_servers