First, which version of the S3 do you have? ( One of the US carriers, or international? )
Typically though this happens when you are actually right on the edge of data service. The phone is barely able to connect to the network, but the connection is not stable enough to transfer data.
So, some things to do are first pull down the notification bar and turn off Mobile Data, wait a few seconds and turn it back on. Then try. If that does not work you need to check with you carrier and see if you are in a poor coverage area. It is also possible the tower you are connecting to is currently having problems.