Galaxy S4 GPS Problem "Please enable Google apps location access" I have a brand new S4 and cannot figure out why the GPS is not working.

In Google Maps, clicking the button that centers the screen at your current location reveals the following error:

"Please enable Google apps location access"


Going to Settings>Location Services I have everything checked off and activated:

Access to my location (let apps use your location information)
VZW location services
Standalone GPS services
Wi-fi &amp; mobile network location service


Is there any reason why it shouldn't work?
Go to Settings>Accounts>Google>Location Settings and turn "Let Google apps access your location" on.