Didn't the antivirus just say it cleaned the infection? So why's it back? Because the antivirus has been taken over by the virus. It can only stop something that it either knows about, or looks like something it's seen before (heuristics). If it didn't catch the virus in the act, it's too late. The warning could have been the virus trying to make you feel like it was removed and not think about it anymore.
But I did everything right!
Most security professionals are brave enough to admit that they've fallen victim to malware once or twice. The delivery mechanisms play on our instincts, and all the knowledge in the world will occasionally fail when we're enticed by something that goes straight to the core of our being.
So you did everything right, and got a virus. Now what?
This is why you back your stuff up
This is why you do it. It's for when all the best practices and precautions fail. Backups are the panic button. You press it and hope your backup scheme was good enough.
You might as well reinstall everything
That's probably not what you wanted to hear. You'll never be sure it's gone unless you restore everything from a clean backup. Find all your installation CDs, get your backup disks, write down what needs to go where and go at it.
You should probably make up a restoration plan in advance of needing it. Even people who always remember to backup often forget to plan the restoration. A restoration plan is a check on the backup plan.
But backing up is hard
It's only hard if you don't plan ahead. As long as you have your operating system and application installation disks, you only need to back your personal files up. This is where good organizational systems shine. If you scatter documents and files all over your hard drive, you'll have a rough time backing up. If you keep it all in a few well-planned paths, you just copy them over to your backup media.
Don't let it happen again
So you've recovered, have your backup and restoration plan, and are more confident. So what now? The best thing you could do is practice not being tricked by deceptive e-mail subjects from malware distributors. Go in to your spam folder and start looking. Seek out lists of common malware spam subjects. If you know your enemy, they're less likely to win again.