Ok, I didn't try tracking on my s4 yet, because I was working abroad for a while, but I had very good results for cycling, running and other activity, using Endomondo and google's very own, My Tracks.
With Endomondo I was able to edit track by mapping it manually, using their online interface. Sometime, bad reception would result in some funny lines, showing me running across buildings. But overall that map worked great, and the app has a massive amount of features.
Regardless tho, if that's Samsung acknowledged problem, I don't think any app will work right till they fix it.