Same problem with t-mobile
I can confirm this problem too. Mine is slightly different, but very similar. I live in the Chicago, IL area using T-mobile with my N1.
When I was on cm 5.0.8 and lower, which was android 2.1 no issues with finding my estimated location just on 3g or edge (no wifi or gps), going to cm6.0 stable and 2.2, didn't really notice any problems but can't confirm (was only on it a day or two before upgrading roms again). Now I'm running miui v11.26 on 2.2.1 and I can get estimated location on edge, but switching to 3g I always get "current location temporarily unavailable." Same thing with the cm6.1 RC 1 and 2, and even older miui like 11.12 and 11.19.
If I use wifi I get a lock right away, and with my apn settings of "default,supl" I get gps fairly quickly too over 3g.
I don't understand how I can get estimated location for edge and not 3g. Its really annoying for apps that use geolocation but don't need gps ie. beautiful widgets, foursquare, etc...
I've tried wipes, different roms, making sure my usa band and/or automatic is selected with phone information using *#*#4636#*#*, network settings with tmobile selected and/or automatic selection, apn as "default" or "default,sulp" I don't get it....and tmobile customer service doesn't know anything as usual....