Você tem um arquivo /usr/share/applications/virtualbox.desktop? Se você não tentar criar um. O meu parece assim:
[Desktop Entry]
Name=VirtualBox
GenericName=PC virtualization solution
Comment=Run several virtual systems on a single host computer
Comment[de]=Mehrere virtuelle Maschinen auf einem einzigen Rechner ausführen
Comment[it]=Esegui più macchine virtuali su un singolo computer
Comment[pl]=Uruchamianie wielu systemów wirtualnych na jednym komputerze gospodarza
Comment[sv]=Kör flera virtuella system på en enda värddator
Comment[ko]=가상 머신
Type=Application
Exec=VirtualBox %U
TryExec=VirtualBox
MimeType=application/x-virtualbox-vbox;application/x-virtualbox-vbox-extpack;application/$
Icon=virtualbox
Categories=Emulator;Utility;