sounds like it could be some adware/spyware problem, it doesnt sound safe...
My first thought too, but the user isnt a total newb...he was complaining to his ISP about them cutting his bandwidth (again) after hes paid for 2mb and getting 512k.
Ill talk him through installing SpyBot & Adware...any other Spyware killers people can recommend...
Or other ideas if the PC comes out clean?