Comment 6 for bug 1726476

I've encountered this too, tracked it down to a problem in the root filesystem's grub.cfg, it contains the line

 search --no-floppy --fs-uuid --set=root

which is incorrect - there should be a UUID appended to this line. Since there isn't, grub tries to find a device with uuid "root" which fails, and it complains.