amd64 virtual machine in virtualbox

From your details I assume you run a 64-bit Ubuntu host, likely Ubuntu 12.04 beta. It is not clear what version of Virtual Box is installed. The at present most recent Virtual Box release is 4.1.14. Depending on your CPU you also may want to enable it's virtualization features in the BIOS (VT-x for Intel, or AMD-V).

• Both, your host, and Virtual Box should be able to run 32-bit or 64-bit Debian as a guest. However support for Linux Kernel >= 3.2. was only added in Virtual Box version 4.1.8.

• Let me suggest you try to update both, your host Ubuntu (at present kernel 3.2.0-24), and Virtual Box (see also this answer).

• The virtual machine from Virtual Box Manager needs to be set to 64-bit in General -> Basic settings:
  

• In addition, for running 64-guests it is recommended to enable the Input/Output in the System -> Motherboard settings for your virtual machine:
  

• In the System -> Acceleration tab we may want to select the hardware virtualization features VT-x/AMD-V of your CPU if supported.