Eu tive o mesmo problema - também usando a imagem oficial da nuvem Xenial - e corrigi-lo adicionando isso ao meu Vagrantfile:
config.vm.provider "virtualbox" do |vb|
vb.customize [ "modifyvm", :id, "--uartmode1", "disconnected" ] # THIS LINE
end
Como resultado, o arquivo ubuntu-xenial-16.04-cloudimg-console.log
não é mais criado na inicialização e o tempo de inicialização é muito menor.