Is this a problem just in one area or does it happen wherever you go?
I had this problem off and on during the summer at my house, everywhere else I went was fine. I would get the same error messages you are receiving. I would show full bars and the data symbol but I couldn't connect. It would just spin and eventually hang, then I'd get the error message. Once in a while the data symbol would disappear. I was having trouble with the edge connection, as the 3G signal was very weak and I couldn't stay connected to it.
I tried a new sim card, they restored my iPhone as new at the Apple store to make sure I had non-corrupted OS update, I reset my network settings, cycled off and on the different bands & airplane mode, I turned off 3G and tried only to use edge, received "phone updates" from AT&T technicians. Apple did give me a new phone to try but it had the same problem.
The most frustrating part for me was that I had uninterrupted data signal for (3) weeks after I got my iPhone and then the data problem started. Nobody at at&t or Apple could understand or tell me why it just stopped. Then we had a wind storm that knocked out service and when it was fixed it the next day, I had my data back.
I was pretty sure it was an at&t network issue, maybe a bad tower, but I was one day from going to the at&t store to get a BB Bold to see if it experienced the same data problems at my house. If you get a new iPhone and it doesn't work, call at&t and see if they can send a technician out to your area to inspect the towers or find the cause of the data signal issues.
Keep us updated if the new iPhone fixes the problem.