I would first turn PC off, reset the router-modem or unplug it for 10 sec and plug it back in and turn PC back on. You might also reset IE8, by
Tools tab > Internet Options > restore Adanced Settings and Reset Internet Explorer settings, next use Ccleaner and restart PC…http://download.cnet.com/ccleaner/
How long after removing Avast did the failure occur?
What firewall do you use?
This could very easily be malware related, if you are surfing (trying to surf) unprotected.
What OS, and what browsers are you using? If it’s only the browsers, it could be a proxy setting. Did you in the past set up http protocol to Localhost 12080 as recommended for older Windows os?