After doing everything and contacting ATT they believe it is a hardware issue. Now I am trying to decide whether to live with the EDGE network and no 3G until the Iphone 5 comes out or get Iphone 4 now. I am eligible for the upgrade. EDGE is slower than 3G for internet but fine on voice calls.
Thanks for the suggestions.