VBoxManage is unable to start vm code NS_ERROR_FAILURE ubuntu 16.04

OK. Figured out the problem here. My kernel modules hadn't been deleted from the previous install of virtualbox when I uninstalled. So when I ran modinfo vboxdrv, it said I was using the kernel drivers for 5.0.4.

I deleted everything in the path to the filename given in the modinfo output and rebooted. Installing virtualbox and starting vms worked after that.

I found that a simple uninstall and reinstall of both VirtualBox and Vagrant solved this issue.

Each of the installers come with a uninstall script for convenience. Run this before installing. Ideally from a fresh boot of your system to ensure VirtualBox is not running.