Your greatest chance for success is formatting and reinstalling windows. BUT here is a couple things to try:
1) When the computer starts, click start-> run_. type “msconfig” (no quotes) Click the startup tab and uncheck pretty much everything unless you are 100% sure you need it (ex if it is from the AVG directory, you might want to keep it.) A good way to tell is if the filename is a jumble of letters (ex fxyztglk.exe) or something too simple (ex startup.exe), UNCHECK THEM! Also goto the Services tab, check the box that says “hide all Microsoft services” and uncheck anything there that looks suspect. Click OK and restart the computer. When it boots back up, click the checkbox in the prompt that comes up and click ok.
2) Download and install CCleaner, and let it run (will get rid of cookies and other crap and save times for…
3) Download & install spybot, update it, run immunizations, and scan with it.
4) Also to be safe dload and install Ad-aware and AVG antispyware and update those and scan with them.
Those steps likely wont fix all your problems because its rarely that simple but give it a try anyway. Another thing you could do is download and install HiJackthis and try disabling stuff that looks strange with that.