No, no...really simple stuff - I meant different carrier radios. First, I would simply flash a new radio...try Verzions or Sprint, something other than Alltel [it seems you've only tried Alltel radios]. You can do this without flashing a new rom or installing anything else fancy. Should take a few minutes.

The "12 radios" thread has everything you need: http://forum.ppcgeeks.com/forumdisplay.php?f=68

You might also toggle AGPS settings in START-SETTINGS-SYSTEM to see if that does anything.

...if that doesn't work, and you want to explore this idea further, you "could" flash back to stock [make sure GPS is working], flash NRG [make sure GPS is still good - see if MyLocation works], if it still doesn't work, try flashing a new radio again on this fresh flash. If it STILL doesn't work...I would google or get back in touch with whomever you found that has the same issue and see if it seems to be carrier-specific or possibly something else.

I'm out for the eve, so PM me if you need more help/direction.