I hate to be the bearer of bad news, but I never had a problem with the GPS in my S4, but today I'm trying to add my work as a trusted location with the Note 5 and it can't find a location. This is with GPS, cell, and wifi all three on.
EDIT: I disconnected from one unsecured wifi network, logged into another secured network, and then the GPS located me quickly.
So, I'm not sure if this was a GPS problem or my phone needed to download something over wifi to get my location, or what. I'll come back if I have any other problems and update the thread here....