I would guess it to be a spyware problem.
While a fresh install will solve the problem by wiping your hard drive clean you will need to take preventative measures from ensuring you don't find yourself in a similar situation in a few months. Surfing the internet without taking the proper precautions will result in endless computer problems like those you have described above.

Aswell as scanning for viruses on a regular basis with a fully updated and reputable scanner you'll also need to scan for Spyware.
Spyware is probably a bigger threat to most computer users than viruses as it is ever present on the internet and can be installed undetected without a user's knowledge.

To combat this ever increasing threat you'll need to perform regular scans with antispyware programs,the two best and free are:
<a href="http://www.lavasoft.com">Ad-Aware Personal Edition</a>
<a href="http://www.spybot.com>Spybot-Search and Destroy</a>

As with anti virus software, to be fully protected you will need to update and scan regularly especially if you use the internet a lot.

Another step you can take is to replace Internet Explorer as your main browser.
<a href="http://www.mozilla.com/firefox">Firefox</a> is a free and much more secure browser that is findign its way into many PCs these days.
It's an excellent replacment for IE and I wouldn't recommend browsing without it.

For viruses I use <a href="http://free,grisoft.com">AVG</a>, also free.

Coupled with common sense the above will keep you relatively problem free.

_________________________________________________

Keep in mind that you will lose any data on your hard drive that hasn't been backed up.
If there is important stuff on it I would try to back it up first, I've learnt this the hard way like most.
If you need any help with the reinstall procedure. just ask