Geek summary: AVGUpd.exe can't pass Ashampoo Firewall when launched within AVG, but works when run explicitly; as a workaround, create a Task to run on startup and every few hours
Firewalls sometimes block antivirus updates, even when all of the antivirus executables have been permitted full Internet access through the firewall. In this case, I hit the problem on a Windows 2000 PC, on which I'd installed AVG 9.0 Free antivirus and Ashampoo Free Firewall.
I searched about this and found several threads at AVG's forums, which usually pointed to an article that lists the AVG executables that should be allowed through the firewall. Other posts elsewhere simply declared Ashampoo as incompatible with AVG.
Even listing every AVG executable in Ashampoo's rules does not fix the issue, which is more subtle than it looks. Specifically, the AVGUpd.exe update tool does work if launched explicitly, but if it is invoked through AVG's general UI, the update fails.
If you run AVGUpd.exe directly, nothing visible happens unless you already have the general AVG dialog open at the time. If you do, then you will see that dialog indicate the update is now in progress, and it works.
The problem may be Ashampoo blocking interprocess communication within AVG (though I had disabled that sort of internal functionality), or failing to recognise when AVGUpd.exe is invoked from AVG's code (perhaps it calls it as a .DLL?).
A fix (aside from ditching Ashampoo, which I'm reluctant to use for the next Windows 2000 PC that needs a free firewall) is to create Start Menu and desktop shortcuts to run AVGUpd.exe, and/or set a Task to launch this when starting the system and/or every few hours during the day. Both approaches appear to work so far.