Comment 33 for bug 403408

I encountered the same problem on a Dell laptop (I can't remember what model, I guess from around 2005).
I edited /usr/lib/grub/grub-mkconfig_lib and commented out 3 lines as follows:

Before:
  if fs_uuid="`${grub_probe} --device ${device} --target=fs_uuid 2> /dev/null`" ; then
    echo "search --no-floppy --fs-uuid --set ${fs_uuid}"
  fi

After:
  # if fs_uuid="`${grub_probe} --device ${device} --target=fs_uuid 2> /dev/null`" ; then
    # echo "search --no-floppy --fs-uuid --set ${fs_uuid}"
  # fi

Saved the file, then upon reboot it worked, but after that reboot it didn't work.
So, I made the change to /usr/lib/grub/grub-mkconfig_lib again,
Changed the permissions of the file to read only (chmod 444)
Then ran dpkg-reconfigure grub-pc (or sudo update-grub might do the trick too).

I can't be sure exactly why the error re-occured after my first attempt, but there's a chance changing the permissions on the file did the trick.

I actually found it quite fun learning more about grub2 :)