Got this error before when installing Xen 4 on Debian Squeeze:
This means that you’re still running a Xen-ready kernel, but not the Xen hypervisor itself and you won’t be able to boot your virtual machines. This is just a boot order issue with Grub. Most likely the xen hypervisor was assigned a 20_linux_xen but you also have 10_linux from your previous kernel. All you need to do is make grub boot from 20_linux_xen.
To change the oder to boot from xen hypervisor just move the first one in order (10_linux) to the end, like 50_linux
Update Warning: Based on feedbacks some people booted into memory test (memtestx86+). This happens when memtestx86+ is also on the grub list and has higher priority (lower number) than your linux_xen kernel. Before you reboot review the list first and make sure order is correct, that is having linux_xen load first before memtestx86+ or other kernels.
When all is looking good you can proceed with reboot:
You should have the xen hypervisor loaded.