I had a strange problem installing a Windows 2008 R2 virtual on a XenServer 5.5 server today. I gave it 2 VCPUs, 2000mb of RAM (there was not enough free to give it 2048mb), 20gb disk and booted off the ISO for 2008 R2, and it just sits there on "Starting Windows", with the CPUs running at a steady 50%. This looks wrong as it normally goes through in seconds.
After a quick trawl through the forums this seems to happen in VirtualBox as well and some people fixed it by changing the memory settings. I did give it 2000mb, which is a bit weird, so I adjusted the other VMs on the server to free up some RAM and upped it to a more normal 2048mb. Booted again and bam, works first time. You know its good because the very un-server animation of the Windows logo appears above Starting Windows and then its all go.
Turned off the machine, set it back to 2000mb, hangs again. 2001mb does not work either, but 2047mb does and so does the relatively inadequate 1536mb - but not 1024mb. I give up trying to find a pattern at this point.
Basically if you get this issue with 2008 R2 on a Virtual, pick a number (any number) and change the RAM to it. It might work.