bjrosen, my suspicion is that by changing to a Master Boot Record (MBR; what GParted calls "msdos") partition table, you've effectively told the firmware to boot in BIOS mode rather than EFI mode. This makes the system work in the way you're probably more familiar with, but it also has certain limits. For instance, to take advantage of an over-2TiB disk, you pretty much must use the GUID Partition Table (GPT), rather than MBR. Thus, your solution might not work for everybody, and you might find it will fail in the future, should you upgrade your hard disk. Also, different EFI implementations use different trigger mechanisms to determine when to use an EFI-mode boot vs. a BIOS-mode boot, so what works on one computer won't work on another.
IMHO, the best way to boot Linux in EFI mode is to use a combination of the kernel's EFI stub loader and either a good
EFI implementation's boot manager or rEFInd,
which is a separate EFI boot manager that I forked from the earlier rEFIt.
Add an EFI driver for the filesystem you use on /boot, and with the right configuration rEFInd will auto-detect your kernels when you add them. This eliminates the need to use GRUB or to modify your boot loader configuration files when you add a kernel. Currently, the biggest problem with this is that the EFI stub loader was added with the 3.3.0 kernel, so most distributions don't yet provide it. Fedora 16 does (as a package upgrade), and it'll eventually work its way into other distributions, too.