I hope this is a solution for others as I had the same problem.
I found many shortcuts were in fact still in C:\Users\USERNAME\AppData\Roaming\Microsoft\Internet Explorer\Quick Launch\User Pinned\StartMenu but not showing in my Start8 Menu.
I checked the security permissions of the start menu folder and found that the system, administrators and MY_USERNAME accounts all had read only access.
I don't know what caused this, but after setting read/write etc. to Allow, everything works fine again.
Regards Kym H
