I've noticed the same behavior with T-Mobile USA (but have no way to try ATT). I found, though, that if I run the Ovi Maps program, I suddenly get a fix and my IM availability publishes my street location as determined by Ovi Maps. Once I close Ovi Maps, it goes back to Searching...

Does anyone know how to read the NMEA data from the internal GPS receiver? Is there an app yet to grahpically display the signal quality from each GPS sat and the current fix quality?