I had a similar problem setting up my S7. After resetting several times and using all the other advice on disabling and restarting google services.
Here is another solution:
1) Log onto Google on your computer. Turn on two step verification to be texed to your phone.
2) Go back to the phone...