It is possible that a parasite of some sort has caused the issue. You should scan for viruses and adware/malware as a precaution. I recommend the following scanners:
Adaware SE
AVG Anti-Spyware
AVG Virus Scan
To restore your programs to the All Programs menu, try this:
Go to Start>> Run. Type in: regsvr32 /i shell32.dll [Enter] or click OK.
Restart Windows.
Your programs should now be restored to the All Programs menu.