I had the same problem using VirtualBox 2.1.4 on my laptop lenovo w500.
Solution came fast end efficient When setting virtual support in bios there is a note to POWER DOWN machine otherwise the change will not work. I shut down the system, turn off AC and switch off battery for a few seconds.
Now I can easily set up guest Gentoo x64 on vista 64 host.
I have found a solution. The problem is in the Virtual Media Manager. You should release the virtual hard disk from the virtual media manager (menu file), and then mount it again from the virtual machine itself. This error occurs because the state of the virtual hard disk is saved and if in there was a incompatibility (in my case when I install microsoft virtualpc), it is saved and it stays there.
Updating my BIOS solved the problem for me. I have an EVGA nVidia 650i Ultra mainboard with a Q6600 CPU. Updating my BIOS was the only solution that worked for getting VirtualBox to accept a 64-bit guest OS (Ubuntu 9.10 under Vista Home Premium 64-bit).