Hello,
I am experiencing the same problem.
When I start Windows10 and having installed free AVAST I will get
either
"CRITICAL ERROR - Start Menu and CORTANA aren't working. W'll try to fix it the next time you sign in."
or
"Schwerwiegender Fehler. Das Menü Start und Cortana funktioniert nicht. Wir bemühen uns, das Problem bis zur nächsten Anmeldung zu beheben." (since I am a german ;-)
The latest Avast version I tried was AVAST 2015 R4 build 2233.
There has been some posting that Avast it not to blame for that. Ok, we all know microsoft products and their quality

BUT that does NOT help me.
The only way for me to work properly is to uninstall Avast.
I would like to have Avast back and I would also like to have a computer that just works when I need it.
How many Avast users are suffering under this problem?
Even so it might not be the fault of Avast, is the Avast team addressing this problem?
Best Regards,
Michael