The desktop icon not starting is unlikely to be to do with your firewall.
Check the option in the Appearance tab of Program Settings.
As a temporary measure you can create a desktop shortcut for this file C:\Program Files\Alwil Software\Avast4\ashDisp.exe (the avast icon and interface to the providers). Right click on the file and select Send To, Desktop (create shortcut).
What other security based software do you have that might block new startup entries, e.g. Spybot S&D (TeaTimer), AdAware (AdWatch), SpySweeper, Spyware Doctor (StartUpGuard), PrevX, WinPatrol, ProcessGuard, etc. ?