On EFI the grub.conf includes a device mapping line that ensures that hd(x,y) points to the right device. This information is pulled from efibootmgr -v, so the new entry needs to be made before writing grub.conf on EFI, not after.
marking as a beta blocker, this bug was effectively voted on and accepted as part of the go/no-go meeting today, in the discussion of #741781.
anaconda-16.20-1.fc16 has been submitted as an update for Fedora 16. https://admin.fedoraproject.org/updates/anaconda-16.20-1.fc16
Package anaconda-16.20-1.fc16: * should fix your issue, * was pushed to the Fedora 16 testing repository, * should be available at your local mirror within two days. Update it with: # su -c 'yum update --enablerepo=updates-testing anaconda-16.20-1.fc16' as soon as you are able to. Please go to the following url: https://admin.fedoraproject.org/updates/anaconda-16.20-1.fc16 then log in and leave karma (feedback).
verified by me, bcl and a few others with RC4.
anaconda-16.20-1.fc16 has been pushed to the Fedora 16 stable repository. If problems still persist, please make note of it in this bug report.