There was a problem communicating with Google servers, try again later - Galaxy s3
I have finally found the solution for this problem and want to share it here for those of you suffering from the same issue that was not answered by any of the steps mentioned in the original post.

In short, I needed to reinstall Google Play Services

In your device ... 


Go to Settings > Security > Check Unknown sources 
Head over to APKMirror
and get the version of Google Play Services that is applicable to the your Android version.
Install
Probably best to reverse step 1 once finished


This worked for me.