Into the firewall settings, the following programs should be allowed to connect:
C:\Program Files\Alwil Software\Avast4\ashWebSv.exe (avast! Web Scanner)
C:\Program Files\Alwil Software\Avast4\ashMaiSv.exe (avast! e-Mail Scanner Service)
C:\Program Files\Alwil Software\Avast4\Setup\avast.setup (avast! Update executable). This is a temporary file that just appears when an update (check) is about to launch, and disappears again afterwards.
Besides this, which is your email provider (GMail?)? Does it use secure connections (SSL)?