Not sure if this really qualifies as an answer, but since I don't have enough points to comment and I do want to contribute what I've discovered about this problem, it'll have to do...
I've had a very similar sounding problem for the last 2 weeks or so with no obvious trigger in terms of app or firmware updates. My location history has gone crazy with some days getting reported travel distances of 10 - 20 thousand miles in spite of me just going to work and back (60 miles each way).
What is happening is that while I am at work, or travelling (or anywhere away from home), location points are being recorded for where I actually am, then for a point very close to my home location, then back where I am again, then back at home, etc. The system seems to be seeing me travelling home and back roughly once per minute, and all those journeys quickly add up!
So far I have tried switching off wifi/cell location services, but that gives you basically no location history and Google Now is largely disabled, so that's no help.
Turning wifi/cell location services back on and then turning wifi off when away from home does help - it gets rid of the 'home and back' in one minute journeys, but the location history is less accurate when away from home. I am using an app called 'Llama' to do this automatically at the moment.
My conclusion from this is that for some reason wifi location reporting is giving a bogus result of 'near home' constantly throughout the day. The only sensible reason I can think of for this would be if I was carrying around another device acting as a wifi access point and that Google location services had learned to location of that wifi point as being at my home. However, I'm not actually carrying around such a device.
Next steps I am considering trying :
- wipe the data associated with the maps app on the device
- wipe the data associated with the wifi app on the device
- do a factory reset on the device and restore
As suggested by GAThrawn below, the most likely cause of this problem is having a second Android device set to report location in addition to your primary device. You take your phone with you, but your tablet sits at home. Both report their location once per minute, or thereabouts, and your location history goes crazy.
The solution in my case was simply to turn off location reporting in the Google maps settings on the secondary device.
I also have a Nexus 4, on T-mobile UK