From the information you've provided, it sounds like you have the device correctly setup to use Google Play Services for location requests.
I'm not sure why Magic Earth is not working for you whilst Google Maps and OsmAnd are. I suggest installing the GPSTest app, and having a look at the results there. That can be quite useful.
Have you tried reinstalling the Magic Earth app? I am not sure it will help, but perhaps the app does some checks only on initial install.