Well by default the Vista firewall has the outbound checking disabled, so that shouldn't be getting in the way unless you enabled it.
The ashAvast.exe doesn't need permission as it is just used to start an on-demand scan (doesn't connect) or to start avast from safe mode, do a memory scan and start the Simple User Interface so that you can run an on-demand scan.
Since the manual scan works if it were the vista firewall blocking then that wouldn't work either. So I would say you need to delay the update check as it might be that although you may have a connection present it isn't fully ready that close to boot.
You need to edit (using notepad) the [InetWD] section of the C:\Program Files\Alwil Software\Avast4\Data\avast4.ini file and add the following line (depending on your connection type enter one or other of the Bold lines below):
Dial-up connections, add this line:
RASWaitSeconds=120Broadband connections, add this line:
AlwaysConnectedWaitSeconds=120[InetWD]
AlwaysConnectedWaitSeconds=120
Or
RASWaitSeconds=120
When complete save the changes, avast's self-defence module will ask for confirmation, etc. answer Yes.
The figure is seconds and the above equates to two minutes, you could try that and adjust upwards if required, 180, 240, etc.