We've seen the same issue here, although so far only on Win7 PCs. As per your experience, a random number of reboots into safe mode does seem to sort it out.
I hadn't considered Avast could be a factor but it has to be said that we've recently moved from Avast 4 to 7 and the problem does seem to have appeared since then.
When the next PC goes I'll try removing Avast and see what happens.