I had a similar issue with a different samsung device before. In my case the issue turned out to be restricted background data. I had turned ristrict background data on to keep from using mobile data unintentionally.
Verify that mobile background data isn't restricted for all apps, or individually for your maps app. Manually restrict any other apps individually if you need.