Due to the unique approach of Canonical to packaging Vagrant boxes, the current Ubuntu/Xenial box has a hardcoded machine name which causes an error when you try to bring up a second VM using the same base box:

A VirtualBox machine with the name 'ubuntu-xenial-16.04-cloudimg' already exists.
Please use another name or delete the machine with the existing name, and try again.

There's a Stack Overflow question about this and a good answer (not the accepted one, the highest-voted one) which helped me a bit but it still wasn't completely clear to me how to fix my problem and I had to dig about a bit.

First, ask virtualbox about the VMs it knows about by doing vboxmanage list vms. My output looks like this:

"ubuntu-xenial-16.04-cloudimg-20160625_1467103387140_3797" {362a5d12-805e-498e-9068-8334b2185701}
"ubuntu-xenial-16.04-cloudimg" {5f366c5b-2526-4e30-bcc2-50ad67c9938d}
"ubuntu-xenial-16.04-cloudimg-20160625_1468498702339_50838" {bb41ec04-2e18-444a-a673-cd7f70f6b3c4

Keep this where you can see it, we'll need it in a moment.

Next, look for a file called (path relative to your Vagrantfile):

./vagrant/machines/default/virtualbox/id

(Note that default here is the machine name of the box, important if you have multiple or named VMs defined in your Vagrantfile).

The file will probably contain the identifier (in the curly braces above) from one of the VMs with a longer name. I found that I needed to replace this with the identifier of the one with the original, short box name—so, in this case, the file simply needs to contain 5f366c5b-2526-4e30-bcc2-50ad67c9938d. After making this change, the error no longer appears.

Tangent: Ubuntu/Xenial Vagrant Box Has No Guest Additions

If you're using this box then one of the other problems you will encounter is that it was packaged without the guest additions installed. Try the vagrant-vbguest plugin to fix that problem as well.

You're welcome :)