Although I have several kernel versions in /boot and having them in my grub.cfg, they are not displayed in the grub boot menu.

Running update-grub seems to work, as it puts the kernels in the grub.cfg in /boot/grub. Issueing it gives the following output:

Generating grub.cfg ...
cat: /boot/grub/video.lst: Datei oder Verzeichnis nicht gefunden
Found linux image: /boot/vmlinuz-3.2.0-31-generic
Found initrd image: /boot/initrd.img-3.2.0-31-generic
/usr/sbin/grub-probe: Fehler: no such disk.
/usr/sbin/grub-probe: Fehler: no such disk.
Found linux image: /boot/vmlinuz-3.2.0-30-generic
Found initrd image: /boot/initrd.img-3.2.0-30-generic
/usr/sbin/grub-probe: Fehler: no such disk.
/usr/sbin/grub-probe: Fehler: no such disk.
/usr/sbin/grub-probe: Fehler: no such disk.
done

I don't know how to fix that problem. Reinstalling grub via live cd did not help.