With GRUB 2, I'm pretty sure that you can use "grub-install" without any options to do the job; however, Fedora uses a heavily modified GRUB Legacy on EFI systems. (Its developers believe that GRUB 2 isn't yet reliable enough on EFI. I agree with them.) I don't happen to have an installation handy with GRUB Legacy set up, so I'm not sure if its EFI version uses grub-install. The package file I just checked doesn't include it; it just places the boot loader binary where it belongs. EFI boot loader installation is much simpler than it is under BIOS; all you need to do is to copy files to the ESP. In the case of GRUB Legacy, the file is called grub.efi, and it normally goes in the EFI/redhat directory on the ESP, which is normally mounted at /boot/efi. Thus, it normally goes in /boot/efi/EFI/redhat in the Linux filesystem. It should have a configuration file called grub.conf in the same place. If this file is missing or damaged, your best bet is to re-install the grub-efi package.
That said, it sounds like your firmware may be attempting to boot in BIOS mode rather than in EFI mode because it's found BIOS boot code in the MBR. To fix this, you must wipe out that code. You can do this with dd:
dd if=/dev/zero of=/dev/sda bs=440 count=1
Type this as root. Be sure to get the bs= and count= options right, or you might end up damaging your partition table or even data in your partitions.
You may want to check my Web page on EFI boot loaders.
It may help you understand what's going on and how to manage your boot loaders. It's really much better than the BIOS system once you understand how it works, with the caveat that some EFI implementations are badly designed and create unnecessary problems.