I've been having the same problem. I've drove to another location to rule out tower, tried other tmobile branded phones, noted other co-workers having the same problem, which ruled out sim card, hard reset my phone, and flashed back to factory rom. The only think I've noticed is if I flash to factory rom or do a hard reset and keep the cooked rom, I do NOT get the error until I install any program... doesn't matter what the program is... but after installing it the first time the error starts again.
It doesn't happen ALL the time, but will happen at least once on every connection.
I'm actually on the phone with Level 3 support at T-Mobile now to see if they can solve the problem. I'll let you guys know what I find.