I got this error today right after I had moved my virtual machine folder to a different drive.
This is what happened. I moved the virtual machine folder off my main hard disk to another disk. I then deleted the listing in Virtualbox and then went to add the machine back. This is where I get the message. A very simple step that was missing was for me to CLOSE Virtualbox and reopen the program. After that simple mistake I was then able to add my VM and start it.