Worked like a charm. Not sure if this helps, but on clearing the data there would be a popup about location services. Clicking on "Disagree" and then checking for update did the trick.
Worked for me, first time...Had to delete Google account then add again.