I'm experiencing the identical problem. I could have written your post.
To add: I contacted ATT and they had some info about towers in my area being worked on. I explained that the problem was not only in one location in the city but multiple (Austin, TX) so that probably wasn't it. They confirmed that all of my iphone 4 OS updates were current and had me reset my phone. They pushed something my way. Nothing has changed and may actually be worse. I have done this twice now. They are supposed to call me tomorrow afternoon to check in. My phone is a company phone so I know the bill is current and also no one else in the company is having the same problem. Usually I'm the lucky one!
If anything resolves itself, I'll check back in.