I started getting exactly the same problem a few days ago. I noticed the red circle on avast! a-ball icon which produced the same error message above when I clicked on it. It also appeared to cause all my Internet Explorer 7 and Outlook Express connections to fail.
The first couple of times it happened, I was able to resolve the problem by doing a system restore to a point a day or so before this all started. I had to do another one late last night, and it was fine up until this afternoon when the familiar "Webpage cannot be found" error recurred, and lo and behold, the dreaded red circle had once more reappeared on the Avast icon. I performed another system restore, and decided to uninstall Avast, then re-install it. Unfortunately, immediately I had completed the uninstall I lost all IE connectivity again so I was unable to connect to the site to access the download. The only thing for it was to do another system restore. However, horror of horrors! this time I was confronted by a message saying that my computer could not be restored to the earlier time.
I started to have nightmares about having to perform a complete Windows re-installation. However I tried logging on using another (non-admin) user account, and although the Avast red circle was still present, I found that I could at least connect to the internet. The next step was to log back in on the admin account and grant the other user account admin rights, then log back in on that and hope it had still had internet access - it did!
I was then able to download and reinstall Avast. I checked that all the startup settings, etc, are on automatic, updated the database, rebooted ...... but still the red circle is there. I have followed all the instructions in the FAQ link from the error message, including the Repair option in change/remove programs, which stated (wrongly) it had been successful, but I am now without any effective run-time virus protection. The only saving grace is that I still have internet connectivity, although it was still dead on the original admin account I used, so I ended up having to delete that account and create another with the same name and attributes.
Being naturally paranoid about my pc being open to infection from viruses and other nasties, I would very much welcome urgent advice as to how this issue can be resolved.