In other words, buying a video card off the shelf at Best Buy does NOT mean it will work in a Mac since it is not supported via EFI BOOT. Makes perfect sense to me.
It looks like PowerColor has actually announced that they'll be shipping UEFI GOP cards. Apple supports EFI UGA, but not the GOP profile. With any luck, Powercolor will support the UGA profile as well (which wouldn't be that hard, but is less likely), or Apple will add UEFI GOP support (much more likely.)
Edit: I'm reading OS X supports GOP? If so, it might be possible these new Powercolor cards would work out of the box. I saw a thread on Netkas with no conclusions.
Edit 2: Yep, it looks like even though Apple isn't using uEFI, they're already using the uEFI video mode (GOP).
Edit 3: It looks like the Mac Pro is the last machine left on UGA, probably because it hasn't been updated. I'd expect the next update would move to GOP, which should add compatibility for the uEFI cards that are starting to be pushed out. Every other Mac is on GOP.