2 possible ways to fix this. One requires system restore to be on and have a restore point from before the infection. For the other you can't have emptied your temp files since the infection messed with your start menu.
There are 2 locations of start menu type of shortcuts:
Applications installed for all users: %Program Data%\Microsoft\Windows\Start Menu
Applications installed just for your user: %UserProfile%\AppData\Roaming\Microsoft\Windows\Start Menu\Programs
1: In some cases the shortcuts are just moved to the temp folder.
%UserProfile%\AppData\Local\Temp\smtmp\1 – these were the missing %Program Data%\Microsoft\Windows\Start Menu items.
%UserProfile%\AppData\Local\Temp\smtmp\4 – these were the missing %UserProfile%\AppData\Roaming\Microsoft\Windows\Start Menu\Programs
You may also want to check out the 2 and 3 folders, I am not sure what links are in there but you may want them too.
2: Go to the various start menu locations. There should be the Programs folder. Right click and go to Properties. Go to the Previous Versions tab. Wait for previous versions to load in window. Click on a version before the virus. Open the folder to verify that the shortcuts are there, then click on Restore and most of the programs will be back in the Start Menu.
Let me know how this does. I think that the first one has the best chance of success but the other may work too.
Corrected for windows 7 start menu and temp file paths. Accidentally put the XP ones in first time.
Edited by Goibniu, 01 June 2011 - 11:43 AM.