You boot with the Debian install CD, and boot the rescue system. Tell it you want a shell, and it will chroot you to the Debian installation. Then you can either edit device.map, or just run grub-install and see what happens. Grub gets device.map wrong frequently enough, that it posts the contents of device.map after it's installed, and asks if it is correct.
|