Even weirder, the icon shows in the short view, but not when it is expanded to 'All Programs', or in the actual Start_Menu\Programs folder.
It seems to be functioning: the taskbar icon rotates and Windows shows the system as protected by Avast.
Curioser and curioser.