Comment 72 for bug 428435

Martin-Éric -- if you need a workaround, try adding 'GRUB_DISABLE_LINUX_UUID=true' to your boot parameters, and changing 'root=UUID=foo' to 'root=/dev/hda1' or whatever your boot partition actually is. This allowed me to boot my machine (which doesn't have an encrypted partition either) after upgrading to Karmic, and finding the same ambivalent signatures problem prevented me from booting.