Ran into this one today, on a debian squeeze box:
/usr/sbin/grub-probe: error: no such disk.
It actually was telling the truth, the disks listed in /boot/grub/device.map were wrong. Replaced /dev/disk/by-id/serial-of-drive with /dev/sda. Worked.
Whilst researching this problem, I did run into a similar debian bug, but it wasn’t relevant. In case you’re interested, it’s about LVM drives, and it’s here: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=673573