I have uverseAT&T U-Verse at home. My s3S3 connected to the gateway with no issues. Did you try to remove the saved network from the phone, factory reset the gateway and then try adding it. If that fails, try to manually add the ssidSSID and key after you remove the network from the phone settings. Worst case ask them to send you a new gateway. If you changed the ssidSSID at any point or added static ipsIPs you might need to factory reset, add the phone and then add the statics to the gateway again.