After wasting a whole day on this problem (using Virtualbox 5.0.12 on Arch Linux), I finally got it solved in the way thomthom's answer suggests. For those who are unsure about the exact procedure, the command which clones an entire machine (including snapshots) is:
VBoxManage clonevm --mode all --basefolder </new/path/> --register <VM_to_clone>
Obtain the VM's name with
VBoxManage list vms
If necessary, quote path and name.
Finally, check if all is well and remove the original.
That's all, really.
No need to bother with xml files or a hex editor. No need to use a GUI, either.
http://www.virtualbox.org/manual/ch08.html#vboxmanage-clonevm