One thing that might help...
Sometimes apps need to have a specific user setting enabled, usually something like "Enable location or GPS services." I don't think Google Maps needs this setting to be on to work (since it is a Google Android phone), but other apps that want to access your location need this setting.
Double check your phone's setting and make sure 3rd party apps are allowed to access your location services.
You might have already thought of this but its just an idea. Good luck!