When troubleshooting, it is recommended to reboot after applying changes or offline updates. A glitch on the database can happen for many reasons, including a downtime of the server.

If you are connected to the internet “permanently”, then change Avast main GUI → settings → updates → “my computer is permanently connected to the internet”. If, instead, you are on dial up, select the appropriate option.

In the settings → updates tab, you also have “direct connection (no proxy)”, which sometimes solves problems with database updates.

Should I try a deep registry clean after removing AIS? Please be sure that the update service is not blocked by AIS firewall and that Windows firewall service has been disabled.

If you used the Clean Uninstall Utility of Avast from http://www.avast.com/uninstall-utility, no more deep cleaning should be necessary. In any case, if you do a registry clean, please avoid doing it “automatically”, as there is a tendency to make more harm than good.

There is a new beta currently in development, so in the near future you should have a new stable version of AIS available for download. If the problems are not solved by then, try:

1_ Backup your registration file,
2_ Uninstall Avast using Add/Remove Programs.
3_ Reboot into Windows Safe Mode and run the Clean Uninstall Utility. Repeat this step for each version and edition of Avast you ever used (including rebooting between each run).
4_ Reboot into Windows Normal Mode and run the latest stable version setup.
5_ Reboot once the installation finishes.
6_ Configure Avast as you need, and REBOOT again.

Now, about firewall and its rules, when troubleshooting it is recommended to delete the firewall rules related to Avast, then reboot and connect again. Usually the firewall should ask you again for confirmation (“learning mode”), so the rules are rebuilt for the new Avast version / release / edition / installation. Even when the rules seem to be correct, rebuilding them usually solves some of the problems. After rebuilding the rules, wait for Avast to finish any updates and reboot.

HTH.