Try a restore in safe mode. Install a third-party firewall if you don't already run one - take careful note of what processes you allow access to the internet, and extremely careful note if you allow "iexplore.exe" and get the adverts again - if that's the case, something is hooked into Internet Explorer and is using it to bypass any firewall software.
Comodo Firewall appears to be highly thought of here, I link to an older version because v3+ includes a full security suite and is 30mb or so; click here
Use Malwarebytes Antimalware or Superantispyware to scan for anything AVG has missed click here . AVG has slipped to the bottom of the freeware antivirus charts for myself and some others here, there are too many things the free product doesn't protect against. Avast or Antivir Avira are better click here .