I signed up last Friday in advance of the iPhone. Tried a Shine. No reception for me. Exchanged for a v9. Much better, but big, heavy, poor battery life. Camera is good. I also considered the Nokia N75. Its supposed to have good reception, good camera, poor battery life unless you change some setting.
I also thought about the Sony Ericson 750. Supposed to have decent reception.
I'm planning to try a Nokia 6555 for my mom as a third phone. Camera stinks, but supposedly good reception and reliable.
So far I've been amazed at how bad AT&T coverage is in NC. Sprint has coverage EVERYWHERE.