Basically, the vCenter Workflow Manager service had stopped on my vCenter server. In my case, I'm running the 6.0.0 vApp so I had to open an SSH session and enter the following:
shell.set --enabled true
service-control --status vmware-vpx-workflow
(this command confirmed the service was stopped)
service-control --start vmware-vpx-workflow
Once running, I was able to start VMs again from vCenter.
Not sure why this was so hard to find in a web search but hopefully the search engines will pick up this blog post and save people some time!
VMware KB: VMware NSX for vSphere 6.x Controller deployment fails the error: Failed to power on VM NSX Controller
VMware KB: Stopping, starting, or restarting VMware vCenter Server Appliance 6.0 services