Clonezilla disk to disk clone on a dual boot ubuntu karmic & XP setup - cannot open '/boot/grub/device.map'

When you want to re-install Grub from a system that you cannot boot, you usually boot from a live CD like Knoppix or Ubuntu. There you mount your Linux installation:

mount /dev/sdbX /mnt

Where X is the partition number on your hard drive. Then, you have two possibilities. Either you install the Grub version installed on your live CD:

grub-install --no-floppy --root-directory=/mnt /dev/sdb

Or you install the Grub version on your Linux installation:

chroot /mnt /bin/bash
grub-install --no-floppy /dev/sdb
exit

If this still throws the same error, you should send us that line of the grub-install script and the lines above it (using head -374 /usr/sbin/grub-install | tail -10).