Both approaches listed under 10.b for using grub fail in an environment using virtio block devices. In these environments, the following must be done: echo "(hd0)\t/dev/vda" >> /boot/grub/device.map On virtio-based systems, this step should happen either immediately prior to code listing 2.6 or code listing 2.7, depending on whether the user takes the primary or alternate approach. This may be true of some other paravirtualized disk environments as well, but I don't know what they would be. Explanation: When using Linux virtio disks, the VM BIOS has no knowledge of them. As a consequence, grub fails to detect them as well. We must tell grub where to find them by adding the line to the device.map file.
Thanks, updated in CVS; should show up on the size in an hour or so