The OP has very likely not got any spyware or malware. Nor is it a spoofed message as it wouldn't have been sent to just his contacts list.
This is happening to more and more users of GMail and Hotmail and I'm sure other web based e-mail systems.
I can't say what has happened apart from suggesting someone or something has gained access to the e-mail account and sent a spam message. I can't say how they/it gained access. The easy suggestion is malware on the PC, or putting your password in to somewhere that has been compromised. While I can't be sure the later isn't the cause, I can categorically rule out a compromised PC.
Until this happens to you, you will be sure the OP has been compromised as that can surely be the only way this happened right? Well, it happened to my GMail account, twice. Now, my PC is scanned VERY regularly for both malware and viruses. I have never accessed the account anywhere other than my main PC. The password is used elsewhere, however the password is not only complex (upper, lower and numerical) but it was changed between intrusions. The password was completely different as well.
So yeah, I don't know what the hell is going on, but I don't believe the user is necessarily at fault.