Сначала удаляем через apt саму программу:
sudo apt-get remove --purge virtualbox
Затем (если требуется) удаляем все виртуальные машины и настройки (у вас они скорее всего лежат по другим путям- проверьте):
sudo rm ~/"VirtualBox VMs" -Rf
sudo rm ~/.config/VirtualBox/ -Rf
Потом можно установить заново:
sudo apt-get install virtualbox
