Did you recently update the kernel? And get a new initrd as well?
I ask because from what I've seen, this is a common problem. When you update the kernel (and a new initrd is created), the initrd doesn't get built to include the xenblk.ko driver.
You can check by unpacking the initrd into a directory using this command:
gunzip < /boot/initrd.img |cpio -i --make-directories
Create a new directory first, cd to the directory, run the above command. Look at the init script. Does it have the following lines in it?
echo "Loading xenblk.ko module" insmod /lib/xenblk.ko
If not, you'll need to move xenblk.ko into the initrd directory (correct version of course), add the above lines and repack the initrd using this command:
find . | cpio --quiet -co | gzip -9 > /boot/initrd-XXXXX.img
Just went through this (again) so it's fresh in my mind. I tried using the mkinitrd command to create a proper initrd in the domU but couldn't get it to add the xenblk driver for some reason.
If the above isn't the problem, I'll bet it's leprechauns.