Chinese hacked my Gmail account!!

Today morning when tried to log-in to my Gmail account, GMail asked me provide a cell number so that they can send a security code via SMS as it seems that the account has been misused. I thought gmail has gone mad and is just freaking out. But to my dismay I saw following mail being sent to all my contacts

Dear friend,
How are you doing now?
I bought a notebook from the website last week www.krrshop.com
I have received the product in time.
Not only its quality is very good,but alsoits price is very low.
They also sell phone,TV,handheld game player,motorcycle and
musical instruments.
They import products from USA, Japan and South Korea,and they import
the bestsellers.
They have a good reputation,and offer the good suggest to the
customers for the purchasing.
If you want to buy any product,it is the good choice to browse the website.
It is conviced that you will get benefits and joys.
Greetings!

I started getting lot of mails from my friends like "Dude how much commision u got for sending this crap", "Is this your new business??"....
At the bottom of my inbox I clicked on the Details hyper-link to see the activity information and to my dismay it clearly showed me that crackers from China had logged in to my account.




I googled about this issue and I could see same happening with few other people, even an Android phone was hacked and same mail was sent through his Gmail account. I had followed following security tips mentioned in Gmail help forum


First you need to check the bottom of the Inbox and make sure your account is not open at any other locations. If it shows additional locations, open the Details window and "Sign out all other sessions".

Account Security:
Settings -> Accounts and Import -> Google Account Settings -> Change Password [pick a new secure password]
Settings -> Accounts and Import -> Google Account Settings -> Change Password Recovery Options [verify secret question, SMS and recovery e-mail address]

Potential Spam:
Settings -> General -> Signature [make sure nothing as been added]
Settings -> General -> Vacation Responder [make sure it's disabled and empty]

E-mail Theft
Settings -> Accounts and Import -> Send Mail As [make sure it is using your correct e-mail address]
Settings -> Filters [no filters that forward or delete e-mail]
Settings -> Forwarding and POP/IMAP -> Forwarding [disabled or correct address]
Settings -> Forwarding and POP/IMAP -> POP Download [disabled]
Settings -> Forwarding and POP/IMAP -> IMAP Access [disabled]