O novo pacote do VirtualBox é chamado de virtualbox-4.2. Portanto, se você tiver o pacote virtualbox-4.1
ou virtualbox
instalado, ele não será mostrado como uma atualização. Remover a versão instalada e instalar a nova deve funcionar:
$ sudo apt-get remove virtualbox
$ sudo apt-get install virtualbox-4.2