Strangely enough, I have experienced the same issue, but on my T-Mobile Moto X! I was screaming at Motorola for faulty GPS this... but seeing this thread, what's the common denominator here? T-Mobile!
Did you find the root cause?
I'm very interested in the solution.