Location Error aftermoving So I moved across the country (to Minnesota from Virginia) and now my location is always incorrect on my device, it shows my old home.  I thought the initial problem was with the wifi but my wife's account shows her location correctly.

I can temporarily fix the issue by setting my location settings on the device to 'device only' but the problem reappears when I revert the setting back.  I already tried clearing the Maps data.  This problem occurs on any device with my Google account.

Any ideas how I can fix this issue?

Edit: This apparently isn't limited to Android devices.  Google maps on the web does the same thing.  If I'm logged in as my account, it reads me as in VA, if I log in as my wife (or incognito), it reads the correct location in MN.
If you keep your settings on "Device only" for a few weeks Google should see the new "pattern" and correct it in their records.

If not, then have Google Maps open while you commute to work every day and your account should quickly establish a new pattern. The Google Now algorithm picks up on patterns but for the same reason it is also stuck to your old location.