Adam, I tried to post this in the bug report you listed above, but I can't remember my login for Bugzilla.
Anyway, I experienced the grub issue attempting to upgrade from 15 to 16 using Preupgrade. After finding this thread, I restored F15 using Clonezilla and tried again with the new Preupgrade RPM.
This time, Grub 2 was successfully installed and I could boot into F16 using the correct kernel.
However, Grub 2 was installed to the MBR rather than where it was originally located - in /dev/sda6 where my F15 installation was. Now I'm left with having to restore Grub to the MBR from my Arch install.
I really think this should be rectified before F16 is made gold. Grub 2 should replace legacy grub, but it should be written to the partition where legacy grub was, not automatically to the MBR.