So you're seeing this when you're out and about and on your providers network? Not on a wireless network?
I had this going on at home when I got a replacement router through an RMA. Google is evidently keeping a database of MAC ID's and my phone kept indicating that I was in Texas when I was on my home network. It eventually sorted itself out but it took several weeks. If I got on Verizon's network at home the map location was correct, when I got back on my network I was in Texas. Might have been Chicago, I don't remember.