Urgent security problem

This problem is likely related to my previous issue, which can be found here:

http://forumserver.twoplustwo.com/48/com...

Basically I just received a call from an Indian guy at Windows tech support that claimed that there has been dangerous behaviour on my computer. He went over some things with me and asked me to open "eventvwr" in the run program. He then pointed out that yellow and red warnings were very bad and a sign that a hacker has installed something on my computer. He then confirmed my CLSID (he read it out to me), I then questioned how I could be sure he was even for MS and he said only they know my CLSID (so I guess I should also contact MS support to verify some of his claims).

I'm going to go ahead and check all of my accounts and change passowords (again) and then probably reinstall Windows. My knowledge of computers is that deep, which is why this is my standard response to solving problems. I would have done this at first, but was told it wasn't necessary. This should fix all my issues right?

Please don't be mad at me if there was some sticky I should have followed, however I think this problem is unique enough that it warrants a thread. Thanks for any input.