Yeah... I'd change your password too.... you know... just in case somebody knows it so you don't have to go through this whole thing again once you get your contacts back....
And for if there's ever a next time... I'd start backing up your contact list once a month or so... just go to Contacts --> Save contact list...
Then enter in whatever you want and put it where you'll remember it.
