Après avoir passé toute une journée sur ce problème (en utilisant Virtualbox 5.0.12 sur Arch Linux), j'ai finalement trouvé la solution de la manière suggérée dans la réponse de thomthom. Pour ceux qui ne sont pas sûrs de la procédure exacte, la commande qui clone une machine entière (y compris les instantanés) est :
VBoxManage clonevm --mode all --basefolder --register
Obtenez le nom de la VM avec
VBoxManage list vms
Si nécessaire, mettre le chemin et le nom entre guillemets.
Enfin, vérifiez que tout est en ordre et supprimez l'original.
C'est tout, vraiment. Pas besoin de se compliquer la vie avec des fichiers xml ou un éditeur hexadécimal. Pas besoin d'utiliser une interface graphique non plus.
http://www.virtualbox.org/manual/ch08.html#vboxmanage-clonevm