Is it possible for an iPhone (or any other device over a cellular network) to listen on a socket and wait for other iPhones to connect over AT&T network (P2P)? We are able to successfully do this over our local network, but not over the AT&T network.
I am not a customer of AT&T, but devices on their 3G network are almost certainly behind some form of Network Address Translation, or "NAT" as it is commonly known.
Given that you want two-way communication between devices that are almost certainly both behind (possibly distinct) NATs, you need some method of traversing the NATs in question. Enter Session Traversal Utilities for NAT, or "STUN" for short. Also look into generic network hole-punching techniques.
There is an Objective-C/Cocoa framework for NAT traversal by the name of TCMPortMapper, under the liberal MIT licence. It provides support for UPnP and NAT-PMP, which may or may not get you all of the way there -- it depends on whether AT&T (or any other telco in question) allow you to request ports.
If the above framework isn't enough, you will have to look into providing a well-known (i.e. on the wide-open Internet) relay server to mediate connections between the two devices. This is the method that is generally employed by services like Skype, Hamachi, Xbox Live and others. Good luck!