Laravel Homestead vagrant up times out

I'm following the official guide for running Laravel 5.1 on Homestead.

But when I try vagrant up it hangs up at homestead-7: SSH auth method: private key and eventually times out with the message:

Timed out while waiting for the machine to boot. This means that
Vagrant was unable to communicate with the guest machine within
the configured ("config.vm.boot_timeout" value) time period.

If you look above, you should be able to see the error(s) that
Vagrant had when attempting to connect to the machine. These errors
are usually good hints as to what may be wrong.

If you're using a custom box, make sure that networking is properly
working and you're able to connect to the machine. It is a common
problem that networking isn't setup properly in these boxes.
Verify that authentication configurations are also setup properly,
as well.

If the box appears to be booting properly, you may want to increase
the timeout ("config.vm.boot_timeout") value.

My SSH keys where generated using this command:

ssh-keygen -t rsa -C "you@homestead"

I'm using Ubuntu 16.04 64-bit, Vagrant 1.8.4 and VirtualBox 5.0.18. Virtualization is enabled in my computer, other boxes boot up without problems.

Tried vagrant destroy and deleting the ~/.homestead folder to start again from scratch, but same results.

Here is my ~/.homestead/Homestead.yaml file.

I'm not uploading the vagrant log file because it's too large for PasteBin but I can upload it compressed if needed.

via Chebli Mohamed