AVG is bloated and like all AV's will NOT remove malicious codecs that are downloaded by the various strains of Antivirus2008.
Malwarebytes Anti-Malware Removes Antivirus:
http://www.download.com/Malwarebytes-Anti-Malware/3000-8022_4-10804572.html?hhTest=1.
Download, install, update and select Full Scan.
Remove all infections that it finds after scan.
Spybot S&D:
http://www.safer-networking.org/en/download/index.html
Download, install, update and Immunize, then click 'Check for problems' then when complete select all and then 'Fix Checked'
Spyware Doctor Free Basic Edition - Realtime monitoring:
http://pack.google.com/intl/en/pack_installer_new.html?hl=en&gl=us&ciNum=12
Its free with Google pack, untick all boxes except Spyware Doctor. Download install, update and run.
SUPERAntiSpyware Free Edition:
http://www.download.com/SUPERAntiSpyware-Free-Edition/3000-8022_4-10523889.html
Download, install, check for updates, then select Scan your Computer, select your drive and select Perform Complete Scan
VundoFix:
http://www.symantec.com/content/en/us/global/removal_tool/threat_writeups/FixVundo.exe
Disconnect your computer from the internet
Run vundo
Restart your computer
Run the tool again to ensure no traces are left.
If there are the reboot into Safe Mode and run FixVundo again.
If your desktop has changed or icons are missing also use:
Wallpaper Hijacker Removal Tool:
http://www.majorgeeks.com/Wallpaper_Hijack_Remover_d4816.html
Note: You should hit all "Repair" buttons even though it may not say "Found!" This will fix a wallpaper hijack everytime if all repair buttons are pressed.
Scan online with Housecall:
http://housecall.trendmicro.com
or BitDefender;
http://www.bitdefender.com/scan8/ie.html
Finally download trial of Windows Live OneCare and Scan:
http://onecare.live.com
If the problem persists, turn OFF System Restore and scan with the above programs in Safe Mode, then turn System Restore back ON and create a new restore Point.
Try using the Wallpaper Hijacker Removal Tool first as it resolves many issues with missing icons, internet connectivity etc.
Download Firefox: http://www.mozilla.com then go to your Programs file and rename Firefox, then try to open it (from the program folder, since you renamed it, the shortcut may not work)