The full error is:
Call "VirtualMachine.Relocate" for object "VirtualMachineName" on vCenter Server "VirtualCenterServer" failed.
Looks like it thinks there was a snapshot left-over from a Backup Exec backup. Yet, no snapshot exists, no file on the datastore. Turns out, it's in the vCenter database...
First hit on Google: VMware KB http://kb.vmware.com/kb/2008957
I unregistered and re-registered the VM in inventory and it fixed the problem. One thing to note: make sure you answer the power-on question as "Copy" and not "Move". Selecting "copy" will cause vCenter to assign the VM a new ID, cleaning up the database.