It's quite possible that the Chinese government hacked your iphone so that they can send out spam for fake Rolexes. But in most likelihood you have a keylogger or browser based password sniffer sitting somewhere in your computer, and you are just a victim of a generic hack. You would have got this malware by installing something you shoudn't or maybe you're running buggy software with a vulnerability. BTW, I'm wondering if your father in law was using your computer recently and had his passwords stolen?
It just seems to me like a coincidence that the upgrade was followed by your G-Mail account being hijacked.
It could be that you have been firesheeped - even though G-Mail uses ssl by default, if you use the same password for something else, trying the same password with your email would the first test any spammer would do.
It could also be a simple phishing scam.
As a matter of fact, there are so many ways for an attacker to steal your password so If i where you i would:
1.Boot my computer from a live CD
2.Change all my passwords
3.Do a clean install of all my computers
If you have a lot of free time, before reinstalling everything you can try and find out which one of your machines is actually infected with malware. Try antiviruses, or maybe sniffing the network for random traffic thats not supposed to be there.
That is probably not enough,
you should also change your habits :
Don't login to your account from public machines/networks.And if you have to - use a live CD/USB to boot it.
Don't install just any software on your computer/iphone etc.. make sure it's from a reputable source
Don't use the same password for everything.
There is a lot more you can do but i think you get the hang of it - just be sensible on when and where you use your account.
Did you upgrade or restore? Passwords are retained when you upgrade, but not after a restore (to prevent a person with access to your backup from extracting passwords from it or loading it onto another device.
This has actually happened -- with the spam mail following the same template as yours -- to at least three Hotmail accounts I know, one of which is my old account and the others my friends'. This was maybe three or four months ago, that is before Firesheep (yes, I know Firesheep is just a pretty UI to a general HTTP sniffer). IIRC, on Hotmail the mails did show up in Sent though. I'll check when I can -- on the bus right now...
I'm fairly certain that the system I used to access that account (approx monthly only, to make sure it didn't expire, just in case) was and is clean.