Under Settings/Locaton GPS Enable checked GPS Device Internal GPS Network Positioning Enable Checked Location Server: supl.nokia.com
Do you have a data connection up?
Might be related to the region. I'm in Austin w/TMO and it works perfect for me both on EDGE and 3G. Or perhaps it is the network settings for your particular data plan? If they have you going through a proxy that could potentially hose up things.
Try a different APN (there's the internet2.voicestream one and the epc.tmobile one...if you have one configured try the other).