Comment 2 for bug 108554

I've found that often this is caused when a disk has multiple partitions, with 2 or more root partitions to support multiple distributions or versions.

For example, on a new laptop that comes pre-installed with Microsoft Windows Vista (UUIDs shortened for clarity):

sda1 = UUID=1 Recovery (7GB)
sda2 = UUID=2 Windows Vista (28GB)
sda3 = swap (2.5GB)
sda4 = >> Extended
 sda5 = UUID=5 /boot (512MB)
 sda6 = UUID=6/ (12GB - Feisty 32-bit)
 sda7 = UUID=7 / (8GB - Feisty 64-bit, Gutsy testing, different distribution, etc.)
 sda8 = UUID=8 /home (remainder)

If the 32-bit install in sda6 is performed first and later a different install is done to sda7, the later install will update sda5's /grub/menu.lst so kopt = UUID=7:

# kopt=root=UUID=7 ro

From then on, any kernel updates or other process that runs /usr/sbin/update-grub will set the kernel options root to the UUID of sda7:

title Ubuntu, kernel 2.6.20-16-generic
root (hd0,4)
kernel /vmlinuz-2.6.20-16-generic root=UUID=7 ro vga=791 quiet splash
initrd /initrd.img-2.6.20-16-generic
quiet
savedefault

The workaround is to manually edit /boot/grub/menu.lst and set kopt to the currently-running root UUID prior to doing updates.

Longer term, /usr/sbin/update-grub should take the current menu entries in preference to kopt *especially* for the running kernel - it couldn't have started if the options were incorrect, assuming no manual over-ride.