Bueno, esto es una tontería al final, pero para que lleguéis antes al final, aquí está el truco.
Después de actualizar Ubuntu a la 10.4 el VirtualBox no se actualizaba desde los repositorios. El error que devolvía es este:
W: GPG error: http://download.virtualbox.org lucid Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY DCF9F87B6DFBCBAE
Después de instalar y desinstalar las claves, los repositorios y todo lo que se me ocurría, el error me daba la respuesta: No encuentra la clave DCF9F87B6DFBCBAE (A vosotros os pondrá otra)
Pues nada, instalar la clave que falta y ya esta!
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys DCF9F87B6DFBCBAE A8A515F046D7E7CF (Aquí ponéis la clave que os da el error)
Por cierto, para instalar VirtualBox desde los repositorios tenéis que hacer esto:
wget -q http://download.virtualbox.org/virtualbox/debian/sun_vbox.asc -O- | sudo apt-key add -
sudo echo "deb http://download.virtualbox.org/virtualbox/debian lucid non-free" >> /etc/apt/sources.list
Hecho esto y si no os da el error de la PGP Signature:
sudo apt-get install virtualbox-3.2
O bien lo instaláis desde el Synaptic.