I know that the information for the start menu and what it shows is kept in the registry. So I took a registry snap shot, then changed some settings in the start menu and then took another snap shot and then compared. The registry key that changed was
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\UserAssist\{CEBFF5CD-ACE2-4F4F-9178-9926F41749EA}\Count\HRZR_PGYFRFFVBA
When I looked at the long vaule of that key I could see text of everything that was in the start menu. So I have a feeling that is the key there.
So since I dont know how to fix that I would sya the thing to do is export out the HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\UserAssist
We are exporting it as a backup. Then once you do that delete HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\UserAssist and then reboot. See if the start menu rebuilds itself or not, if anything goes wrong just import the reg file we exported back in

The reason why this might work is I checked the registry of the default account in windows that all new accounts get copied from and that registry key isnt in there, so it is a key that is made after the user logs in, so we should be able to remove it and have it rebuild itself.
Let me know how that goes.
Shane