maybe even a yahoo one instead of google.

Next is to go to every site you use and change the mail contact to that new account, thereby blocking him from requesting password resets on all of them. Do this IMMEDIATELY!

Send everyone a second new account to be used for friends and family. Reason you want a second account is you may not know who hacked you, and it could be one of them or someone who had access or already hacked them. But do this ONLY after you changed your other accounts to the first new email account. (banks, paypal, purchase sites like Ebay, Amazon, Walmart, etc.)

You might even consider a third account to be used only on social sites like Facebook, MySpace, Youtube, etc

Only after doing all that waste time on trying to recapture that google account. For that have it send a password hint or reset or whatever it does to the last alternate email you had registered with it.