There is a possibility that the connection although present it either isn't fully established or in some cases the firewall can block outbound activity until it is fully running (Comodo is one).
I assume you have a broadband connection, so you can delay the update check.
You need to edit the [InetWD] section of the C:\Program Files\Alwil Software\Avast4\Data\avast4.ini file and add the following line:
Broadband connections, add this line:
AlwaysConnectedWaitSeconds=120[InetWD]
AlwaysConnectedWaitSeconds=120
The figure is seconds and the above equates to two minutes, you could try that and adjust upwards if required, 180, 240, etc.