IE, Firefox, Chrome and update issues

Hi
I have been having issues with browser and program update connectivity since I downloaded AVG free a few weeks ago. I still have internet connectivity as opera works, email client and messengers are all fine. I can also download files, with the exception of update files and online installations.

I have since removed AVG using the AVG removal tool.
I tried a system restore
I have tried reinstalling the browsers
I have tried reset of TCP/IP
I have run several scans, including spybot, avast and malwarebytes. Nothing shows up.
I'm using Vista 64bit premium.

I have read millions of threads and am at a loss now. Any further suggestions would be most gladly welcomed as the lack of function is starting to annoy me (and I really want to try googlewave)
Thanks