Running this on the command line unlocked the VM:
vboxmanage startvm <vm-uuid> --type emergencystop
Where <vm-uuid> is the number in the error message: Command: ["modifyvm", "<vm-uuid>" [...]. After that I was able to control the VM (start, halt, etc).
Using Virtualbox 4.1 on Ubuntu.