Comment 43 for bug 358654

I also had this problem. The solution was to stop grub from using UUIDs. For me using Grub 2 this meant editing /etc/default/grub and setting "GRUB_DISABLE_LINUX_UUID=true". Unfortunately this does not fix the core problem, but it does at least allow you to boot.