Здесь есть несколько проблем, связанных с этим:
Пакеты VirtualBox из репозитория Ubuntu имеют разные имена для пакетов из репозитория Oracle. Когда вы устанавливаете пакет, Ubuntu автоматически устанавливает дополнительные рекомендуемые пакеты, если вы не укажете опцию --no-install-recommends. Существует ошибка, влияющая на пакет Vagrant, что означает, что он заменяет пакеты Oracle VirtualBox пакетами Ubuntu при установке.Я предлагаю вам:
Очистить все ваши пакеты Vagrant и VirtualBox, как вы описали в своем вопросе. Установите последний пакет Oracle VirtualBox, как вы это делали. Установите последний пакет Vagrant с сайта http://downloads.vagrantup.com/, обратив внимание на то, какие дополнительные пакеты он пытается установить или удалить, и при необходимости указывая --no-install-recommends.