What other security based software do you have that might have an effect on boot, e.g. anti-spyware applications, SpySweeper, Spyware Doctor (StartUpGuard or OnGuard), PrevX, WinPatrol, ProcessGuard, etc. ?

If nothing has changed on your system (new security applications or updates) prior to this problem:
Try the Program Settings, Troubleshooting and check the ‘Delay loading of avast! services after other system services’ and see if that has any effect.