On my VPS (running Debian 6.0 on Xen with PyGrub) I get the following error when trying to upgrade the system:
Searching for GRUB installation directory ... found: /boot/grub warning: grub-probe can't find drive for /dev/xvda1. grub-probe: error: cannot find a GRUB drive for /dev/xvda1. Check your device.map.
I googled and found this solution:
echo '(hd0) /dev/xvda' > /boot/grub/device.map mknod /dev/xvda b 202 0
Apparently that only works on older systems and not on my server.