Comment 12 for bug 756564

Booting from a Live CD and `sudo grub-install --boot-directory=/media/xyz /dev/sda` (I've got a separate boot partition) fixed this problem. Afterwards, the device.map file didn't exist anymore.

I cat'ed /var/log/dist-upgrade/apt-term.log and /var/log/dist-upgrade/20110502-1000/apt-term.log together and attached it. Only the former has the errors I remembered before, it seems like the latter continues afterwards. These are the relevant lines:

Setting up grub-common (1.99~rc1-13ubuntu3) ...
Installing new version of config file /etc/grub.d/00_header ...
Installing new version of config file /etc/grub.d/30_os-prober ...
Installing new version of config file /etc/grub.d/20_linux_xen ...
Installing new version of config file /etc/grub.d/10_linux ...
Setting up grub-pc (1.99~rc1-13ubuntu3) ...
Installing new version of config file /etc/kernel/postinst.d/zz-update-grub ...
Installing new version of config file /etc/kernel/postrm.d/zz-update-grub ...
Installing new version of config file /etc/grub.d/05_debian_theme ...
Replacing config file /etc/default/grub with new version
/usr/sbin/grub-probe: error: cannot stat `/dev/disk/by-id/ata-WDC_WD3200AAJS-22B4A0_WD-WCAT12038234'.
Generating grub.cfg ...
Found linux image: /boot/vmlinuz-2.6.38-8-generic
Found linux image: /boot/vmlinuz-2.6.35-28-generic
Found initrd image: /boot/initrd.img-2.6.35-28-generic
Found linux image: /boot/vmlinuz-2.6.35-27-generic
Found initrd image: /boot/initrd.img-2.6.35-27-generic
Found memtest86+ image: /memtest86+.bin
File descriptor 40 (/var/log/dist-upgrade/history.log) leaked on lvs invocation. Parent PID 26922: /bin/sh
File descriptor 44 (/var/log/dist-upgrade/apt.log) leaked on lvs invocation. Parent PID 26922: /bin/sh
File descriptor 74 (/var/log/dist-upgrade/apt.log) leaked on lvs invocation. Parent PID 26922: /bin/sh
done
Setting up grub-gfxpayload-lists (0.2) ...