I'm embarrassed to say this but this one stumped me for a day before I realized what was going on. VirtualBox doesn't really help the situation either, since it never offers you an option to change the architecture so you're left to figure this out on your own. Here's the issue, if you haven't guessed by now.
After going through the wizard to create a VM you'll need to attach the downloaded ISO to your newly created VM. No big deal, this is accessible under the "Storage" menu item under the "Settings" for the new VM. Now start up the VM.
If you select "Live (amd64)" your VM will seemingly hang without any notification of what's gone awry. However if you reboot it and this time select "Live (amd64 failsafe)" you'll get a huge clue as to what's wrong.
Here's where you say "DUH!". So if we change the VM's architecture to 64-bit we should be OK. Here's how.
Changing a VM's architecture to 64-bit
First go back to the main window of VirtualBox, and select "Settings".
From here you can access the various hardware settings for a given VM. We're going to change the architecture settings to 64-bit, which are under "General".
Now pull down the "Version" pull-down and change it to "Debian (64 bit)".
Now you should be using the correct architecture, 64-bit.