Most likely it's just system overload. I travel a lot all over the US and in every area noted in this post. I always have EDGE coverage in all areas. I have been a long time AT&T/
Cingular customer and have had no coverage problems or drop outs. The iPhone is a very major launch that is in addition to the thousands of phones that AT&T sells every businesss day through the stores and the businesss reps. So they are adding many thousands of phones per hour everyday. Then add to that the iPhone explosion and it's no wonder that there are delays.
Be patient. In a few days things will be back to normal.