You make it sound like a common issue when you say "the dreaded start menu issue". Yet this is the first time I've heard of this particular issue.
Always format when installing a new version of Windows.
It's definitely a common issue.
I sit with a similar thing.... the context menu on the start bar will stop working randomly.... the Bluetooth driver causes weird issues, there is no context menu on Windows explorer's shortcut... the start button won't work (on my keyboard).... the on-hover event won't work either. Come restart, and the issues are gone for an hour or three.