Primeiro, obtenha o ID da máquina
# Before v1.1
# MACHINE_ID=$(awk -F\" '{print }' .vagrant)
# After v1.1
MACHINE_ID=$(cat .vagrant/machines/default/virtualbox/id)
Desligue a VM
VBoxManage controlvm ${MACHINE_ID} poweroff
Em seguida, inicialize a máquina com um console GUI
VBoxManage startvm ${MACHINE_ID}
Aguarde que inicialize, faça login, execute:
sudo update-grub
Quando tiver sucesso, desligue-o
VBoxManage controlvm ${MACHINE_ID} poweroff
Depois disso, o vagrant up inicializará sua VM normalmente