Asumiendo que estés usando la versión 3.2, tendrás que ejecutar el siguiente comando:

sudo apt-get remove virtualbox-3.2

El nuevo VirtualBox 4.0 aún no está disponible en los PPA de Ubuntu, así que tendremos que instalarlo manualmente. Para esto, descarga el archivo VirtualBox .deb así como su paquete de extensiones.

Instala el VirtualBox .deb, lo abrimos y vamos a “File|Archivo -» Preferences|Preferencias” y en la pestaña de “Extensions|Extensiones” hacemos clic en el botón “Add|Añadir” en su derecha (primer diamante azul). Luego buscamos el paquete de extensiones que previamente descargamos en el paso No.1 y… VirtualBox está listo para ser usado!

Como ya dijimos, VirtualBox 4.0 aún no está disponible para ser instalado desde el mismo Ubuntu o sus PPA, no obstante, tan pronto esté disponible lo avisaremos.

Este detalle lo añado yo, ya que el paso No.3 no explica muy bien el proceso de instalación:

Para instalar VirtualBox 4 .deb, una vez hayamos descargado el archivo correspondiente a nuestra distro, instalarlo es realmente simple.

Hacemos doble clic sobre el archivo que recién descargamos, nos pedirá nuestro password de administración y, listo. Una vez lo pongamos y presionemos [Enter], demorará unos 5 minutos y tendremos VirtualBox 4.0 instalado. Luego, debemos continuar instalando como se explica el paquete de extensiones.

Y eso es todo.

Fuente: Blog de Kzkggaara