I think I’m in an uncommon situation, but I needed to set up lots of HVM (full virtualization) hosts on my Xen install, since the dom0 is a different distribution (debian) than the domU hosts (Fedora). With paravirtualization, the “balloon driver” takes care of memory allocation, I think. But in HVM mode, you actually have to have the amount of memory required by your VM available outside of dom0. If you don’t have enough, you get an error like this:

Error: Error creating domain: (12, ‘Cannot allocate memory’)

It took forever to figure this out, but the key is to limit dom0’s memory, so that you have enough for your VMs. The machine I’m working with has 16 gigs, so I limited dom0 to 1 gig by using this line in the menu.lst for grub:

kernel /xen-3.0.3-1-amd64.gz dom0_mem=1024M

Yours will probably look different, but the key is the dom0_mem parameter. Once you add that, you will have 15 gig left for allocating virtual machines.