If you have the latest version of the GOOGLE PLAY STORE app on your phone(Version 4.1.10),the issue should
have been resolved.
There was some kind of bug w/this & GOOGLE PLAY SERVICES (current version varies with device).
Google Services Bug Causing Location Issues For HTC Owners, Google Working On A Fix
Perhaps uninstall the updates to either/or of these apps & re-install if you're still having location services issues.Sometimes this will clear things up w/a misbehaving application.
I'd start w/the GOOGLE PLAY STORE first,as you be able to update to the latest version immediately.
As for the GOOGLE PLAY SERVICES,I've read that if you uninstall the updates to this app,you may
have to wait awhile for the latest version available for your phone to be pushed through.
So,before attempting this,you might want to GOOGLE search or check w/GOOGLE's help section/forum for info,as there is a discussion open on this very topic (& apparently a fix as well).