Deve haver alguns arquivos quebrados que precisem ser limpos. Como você desinstalou o VirtualBox? Tente executar o seguinte comando para limpar a instalação:
sudo apt-get autoremove
sudo apt-get --purge remove
sudo apt-get autoclean
sudo apt-get -f install
sudo apt-get update
sudo apt-get upgrade
sudo apt-get dist-upgrade
sudo dpkg --configure -a
Se ainda não funcionar, você pode postar a saída de
dpkg --list | grep virtualbox-qt