AT&T has long had a chip on its shoulder when it comes to video chat apps running on its network. It took a few years to enable Apple's solution, but Android users were stymied just last week when the new Hangouts app refused to connect to video calls over AT&T's 3G and 4G. The rationale the carrier is using to justify its decision is incredibly convoluted, to say the least. However, things are going to change in the second half of 2013.
AT&T makes a bizarre distinction between apps that are downloaded, and those that are included on the phone. Hangouts replaces Talk, so even though it's new to Google Play, AT&T considers it a pre-installed app.