I started using the Nike+ GPS app on my iPhone 4 (not 4s) to track my running in summer 2011. The GPS measurement of runs was pretty consistent: runs on the same course would vary as much as a tenth of a mile from run to run, but I know GPS is not always as accurate as it is precise, so that doesn't bother me.
Sometime in September of this year (2012) the accuracy of my run tracking went way down. I had a few where the distance was under-measured by as much as 50%. I thought it might have been Nike+, but I installed Strava Run and had another run massively over-measured. Last weekend a 6-mile run (measured using gmap-pedometer.com) was measured as 0.17 miles on Nike+. (The Nike+ app, to its credit, has been regularly warning me that the GPS signal is "weak", so even it is dubious about the quality of its data.)
However, in non-running applications, location services seem to be just fine. Maps places me in the right place. Weather apps (Dark Sky is my best example) know exactly where I am. Are they using something else to get my location? Reading this question and this one make me think this could be a hardware problem, but the inconsistency between apps puzzles me.
ETA: I have not yet installed the iOS 6 update, so this is still iOS 5.