I was getting GPS issues for quite some time, until I tightened the screws at the back of my case. It was supposed to be a fix for the S3 but it worked fine on my S4 as well.

Hope this helps