Certek,

I noticed that you mentioned a Firewall. Which one do you use?
I had a similar problem using Sygate5.0 and Avast4. If you use a Rule based firewall, the permissions (rules) must be set properly or Avast 4 will be blocked. An Application firewall such as Zone Alarm works just fine with Avast 4.
Your firewall should not block ICMP type 8 traffic, or TCP traffic on port 80. Usually, your firewall should list 3 outgoing files for Avast in the traffic log (or similar in your fw):
www.avast.com
www.asw.cz
www.iavs.net
Your firewall must allow these destination hosts.

Try shutting down your FW for awhile to see if Avast 4 updates to verify that the FW is the culprit here not Avast 4 itself.

Also, go into your Settings, Update section. The Database should have the automatic box checked and under Program, the ask box is checked by default.

Good luck.