Did Apple degrade the accuracy of the iPhone 4S GPS compared to the iPhone 4
My experience helping others with this problem seems to suggest a few things:


Apple's been monkeying around with power conservation by trying to give "good enough" positioning results while idling the GPS for longer periods and relying on cell tower and wifi positioning more.  Try turning off wifi for your next run to see if the GPS does better (and if your battery is drained more).
Application developers are decreasing the GPS resolution of their apps in order to have less impact on the battery due to user complaints.  Check to see if the app you use can be configured for GPS update frequency and ask the app developer what they suggest regarding your problem.
Both the iPhone 4 and 4S seem to suffer from GPS degradation after awhile that can be fixed by doing a refresh of the device - in other words sometimes it's a software issue that seems to fix itself after a hard reboot and system refresh.  For some people a hard reboot is sufficient, but others have indicated that only a refresh will work for them.  I think this started affecting some of my friend's phones around the beginning of last summer.  I've seen several of my friends have this issue, visit the store, have it refreshed and reset, and the problem disappear.  Now they do the refresh themselves with iTunes when it gets annoying.  I don't have information on whether this is tied to a particular version of iOS or not, but I have seen it on both the 4 and 4S.


Of course you could also be experiencing a hardware problem, but you might consider some of the above actions before completely blaming the hardware.

Also be aware that GPS requires good line of sight to the sky.  If you've changed your iOS device position recently, consider changing it back.  If you're wearing it, make sure your body isn't between the device and the sky, and that your perspiration isn't reaching the device.