Location Error aftermoving
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.