However, irishtenor has a Compaq with a Celeron and said his problems with Windows98 cleared right up with a utility that would "clean" unwanted files from his hard drive (like those banner-ads, etc.). That might be a better option than reformatting your hard drive if it'll work.
I'm not sure what the name of the software was, so I'm pinging him--maybe he can get back to you overnight and give you some pointers.