I'm not sure if this information will help people who are experiencing this GPS issue, but hopefully it provides some useful info to help troubleshoot the problem.
I have a white iPhone 6 and my wife has a black iPhone 6, both purchased in Oct 2014. My phone has been fine but my wife's phone's GPS stopped working, exhibiting the same problems that most people have mentioned on this thread. I contacted Apple support and also brought it to the Genius Bar, only to be offered a replacement phone for $299.
In conducting further troubleshooting myself, I noticed that if I launched the Compass on both phones and put them down next to each other on a table, the white phone would go into calibration mode after a few seconds but the black phone would not. Plus, the Compass coordinates would be different. I checked all Compass settings and they were identical.
As my wife relies heavily on GPS for her commute, I backed up both phones and swapped them out, so now I have the black phone and my wife has my white phone. (We're both on iOS 10.0.2.)
The result of the swap? The black phone continues to have GPS problems while the white phone is fine. The issue stems from the device, as I was thinking it was possible that there was some incompatible app causing a glitch that might be responsible for the GPS issue.