Trying to start VM encounters "Cannot run VM. VM is running" although the VM is showing as down in the RHEVM GUI

Issue

• Can't start VM and popup window says "Cannot run VM. VM is running", however the VM status is Down in the RHEVM GUI
• VM isn't running on any of the hypervisors either
• Seeing this message in /var/log/ovirt-engine/engine.log:

2013-12-02 19:00:53,674 INFO  [org.ovirt.engine.core.vdsbroker.IsVmDuringInitiatingVDSCommand] (http-/0.0.0.0:8443-6) START, IsVmDuringInitiatingVDSCommand( vmId = 55e63ccf-851d-4353-9354-a3132bfac8af), log id: 69c894f6
2013-12-02 19:00:53,674 INFO  [org.ovirt.engine.core.vdsbroker.IsVmDuringInitiatingVDSCommand] (http-/0.0.0.0:8443-6) FINISH, IsVmDuringInitiatingVDSCommand, return: true, log id: 69c894f6
2013-12-02 19:00:53,675 WARN  [org.ovirt.engine.core.bll.RunVmCommand] (http-/0.0.0.0:8443-6) CanDoAction of action RunVm failed. Reasons:VAR__ACTION__RUN,VAR__TYPE__VM,ACTION_TYPE_FAILED_VM_IS_RUNNING