He fet el que deies, però ja tenia instal·lats els 2 paquets.
La solució ha estat fer córrer el Virtualbox des de la terminal i ha protestat aconsellant que baixés el paquet linux-headers-generic, i ha fet:

S'han instal·lat els paquets següents:

linux-headers-2.6.27-9 (2.6.27-9.19)

linux-headers-2.6.27-9-generic (2.6.27-9.19)

linux-headers-generic (2.6.27.9.13)

He reiniciat (re setup) i ara ja em va bé el Virtualbox.

Gràcies,