I want to share my experience with my Note 3 GPS never locking on to the GPS satellite signal until I watched this video. (Android Central would not let me post a video link so I am going to leave the name of the video at the bottom). I know this is a Note 4 thread, but in principle it's the same problem and fix to your phones. I had the same problems as everyone else on my Note 3. I've read this thread from top to bottom because it was the first Thread I found about Samsung Note Phones GPS issues. I suspected all along it was an antena issue, but never thought a ground issue not making good contact could be the reason why I never had good GPS reception.
Since the very beginning, I had a hunch that the problem was reception and had to do with the GPS antenna. I confirmed it when I installed the GPS test application and saw that the GPS satellite signal reception was very much weak and sporadic and it would never lock on or get a GPS fix.
After watching this video I found on youtube, I ventured into opening my Note 3 and figuring out the antenna configuration, which pins where which antenna and so on. Also, I cleaned all contact points and ground points on the main board, casing, housing etc. After I put it all together, the son of a gun works Perfectly...
On the video, this guy is working on a Gallaxy 3, but in essence, it's basically the same. If you go through all the trouble of opening up your phone, might as well learn what does what inside of it.
Since I cannot post videos, here is the name of the video. Search for it. It's 21 minutes long, and it will show you how to troubleshoot and fix very easily with no special tools or training. Here is the name:
"Galaxy S3 Gps Fix (When Screw Tightening Doesn't Work)"
Watch it entirely, don't skip any part of it. The Devil is in the Details! Remember that phones are exposed to condensation, temperature changes, humidity etc.. In your pocket is gets bumped on, hot, cold, expand, contract, get bent, squished, get sweaty and so on. In short something within your phone is bound to get loose and corroded eventually. The video shows you how to figure out if it's Hardware or Software (more than likely hardware).
I have functional GPS on my Note 3 for the first time in almost 2 years

! I'm sure it's the same assembly issue with the Note 4 as well. Sure hope this will help the majority of everyone else.