One of the guys I work with had an issue where the GPS could never find a satellite when using Maps or any other gps based application. What ended up being the ticket was removing other 3rd party applications that used the GPS one by one until the problem was resolved. The app that was causing the issue was "Navigation To Go". Now, I'm not saying that there's a problem with this application... it just was the cause of the problem for one person I know.
So, I suggest removing 3rd party apps that use GPS (if any exist on your device) and see how that goes.
Good Luck!
yes you want both standalone GPS services checked as well as google location services checkedYes.. Which seems to do the same thing as simply clicking the button in the shade/pull down menu.. Still having the same issue.
To clarify I clicked Settings > Location and Security > Standalone GPS Services