пробовали как оно вам посоветовало - увеличить в Vagrantfile например до 10 мин ?
Vagrant.configure(VAGRANTFILE_API_VERSION) do |config|
... другие настройки
config.vm.boot_timeout = 600
что сам инстанс говорит когда загружается ?
у некоторых xenial был замечена задержка с инициализацией network device в первый раз (не каждый раз поэтому не могу точно процитировать ошибку). увеличить timeout самый простой способ. или перейдите обратно на trusty (если у вас ubuntu