Apple, not AT&T, is restricting Skype over 3G, according to Skype blogger Peter Parkes.
Parkes wrote in to 9to5Mac to clarify a few things regarding the latest release of Skype for iPhone.
First they are working on Push Notifications and it will be coming very soon, "we’re working on this; we’ll release a version with Push notifications when the experience has been perfected."
Also, enabling VoIP over 3G isn't being limited by AT&T, "Many of you have also been asking when we'll release a version which allows you to make calls over 3G - the holy grail of Skype on the mobile, if you like. We've had a 3G-capable version ready for some time now, but Apple's current restrictions mean that they won't allow us to make it available on the App Store for the moment"
This only happened to this new version. On previous version, I have always been able to place VOIP calls because there is no restriction in Hong Kong (although the same is not true if I am roaming elsewhere) but the new version put a stop to it. What a bummer! Wish I had not upgraded.