Today I was getting this error when installing a new kernel on a server running Debian:
/usr/sbin/grub-probe: error: Couldn't find PV pv2. Check your device.map.
The error can be reproduce by running the update-grub command.
The day before, a new RAID disk was added to this server, so I suspected this could be the cause. The file /boot/grub/device.map contained a reference to the first RAID disk as (hd0) but did not contain a reference to the new RAID disk. I ran
# ls -l /dev/disk/by-id/
to find out which SCSI ID referred to sdb (the new RAID disk), and then added the following line to device.map:
Now installing the new kernel works fine!