Yikes! Hope you get it fixed up again. All the advice you need is already posted here. Change your passwords on a clean computer, consider the possibility that the password change mails were themselves just attempts to get you to click a link and log in yourself (thus actually stealing your password in the process).

The malware these days is so sneaky that I wouldn't even try to detect and clean it with antivirus. If you suspect there may be something sneaky on your computer, boot off a CD, format it and start with a clean install. Then put good antivirus on, before you install anything else or copy your docs back.