this kernel requires an x86-64 CPU, but only detects an i686 CPU, unable to boot

Using Virtualbox (4.3.6) on an XP64 machine, I ran into the following error while trying to install a 64-bit version of Ubuntu:

This happens even if the host machine is a 64-bit machine. To fix this, reboot the box and enter the BIOS. Look around for a virtualisation setting and enable it. Save and exit the BIOS configuration screen.

When you reboot back into Windows (or whatever, I guess), start Virtualbox again. In the settings pop-up for your VM, you should now be able to change the OS Version to Ubuntu (64 bit), a previously non-existent option. Switch to this and boot up the VM and everything should be peachy.