I just moved, and I noticed that all of my Google Now addresses were wrong (i.e. “7 minutes to home” was actually pointing to my old address). I updated my Google Contact, but it didn’t seem to take. It turns out you need to go to Google Maps and update it from there.
Click My Places and you should see Home and Work. Click the downward pointing triangle to the right of each of these, click Edit, and enter your new address.
Google, if you’re listening, this should be more intuitive. Why don’t those values get pulled from the Google Contact that I’ve identified as me? Then just propagate those changes outward.