virius/trojan?

I installed W2K pro on a new hard drive on a friends computer, Installation went fine. I made a mistake of hooking it up to the net before installing antivirius, antitrojan ware. About 2 secs after clicking IE this pop up appeared:
messenger service

Your register ie corrupted To repair it click this link
www.registrycleanerxp.com

It also promised to stop nagging if you download the program. Other pop ups using the same line but with different urls:
www.clean32.com
www.fix64.com
I installed AVG and Adware, upgrading them both but it hasn’t stopped the popups. I think this may be a trojan. I need help in removing this.

Thanks in advance!