I've been bitten by grub upgrades and installations on Debian family domU servers. Apparently there are others out there who have been bitten too.
The bug itself is caused by a missing device entry, probably because of udev. Anyway, grub-probe tries to discover the root device so that update-grub can properly generate a menu.lst. In certain scenarios the root device itself doesn't exist. Here is an example from a configuration generated with xen-tools:
Hydrogen:/etc/xen# grep phy Neon.cfg disk = [ 'phy:Local1/Neon-disk,sda1,w', 'phy:Local1/Neon-swap,sda2,w' ]
While this is a valid configuration, the device sda doesn't exists within the virtual machine. As a workaround the above blog entry suggests manually adding the sda device and the device entry in device.map.
This solution does work, but it will fail with the next upgrade. The proper solution is to adjust the Xen configuration so that the root device is created. And since Xen uses different naming scheme for devices we can upgrade to that too. So the above example becomes:
Hydrogen:/etc/xen# grep phy Neon.cfg disk = [ 'phy:Local1/Neon-disk,xvda,w', 'phy:Local1/Neon-swap,xvdb,w' ]
You also need to adjust the existing grub configuration and fstab within the domU. It's a bit more work and requires an additional reboot, but it gives you a peace of mind that the next upgrade will work without a hitch.