If you aren't able to boot into an existing Ubuntu installation, boot the Ubuntu LiveCD (same version as the one you want to boot from), then mount the Ubuntu partition and reinstall Grub 2. This will point the MBR back to the Ubuntu boot files. Change X to the proper boot drive (a,b,c, etc) and Y to the correct Ubuntu partition (1,2,3, etc). Don't use the Y value in the second command.
After rebooting from the Grub 2 menu, run "sudo update-grub" to see if it picks up the Fedora installation.
sudo mount /dev/sdXY /mnt
sudo grub-install --root-directory=/mnt /dev/sdX
sudo umount /dev/sdXY
Note: Fedora 15 and earlier use Grub Legacy but Fedora 16 finally upgraded to Grub 2.