med22, If you go to the link below and scroll down to line 154 (right column) you'll see "Remove "All Programs" from Start Menu - Undo". You could click on the underscored word "Undo" to download a reg file fix. Save the REG File to your hard disk. Double click it and answer yes to the import prompt. It may correct the problem.
I'd recommend that you create a new System Restore Point prior to running the above reg file fix.
I was recently badly infected by a virus and have eventually managed to clear my PC with the help of several anti-virus programs. I've managed to restore everything except one, and that is that the "All Programs" button is missing from the start menu. I've tried everything I know to get it back but cannot seem to find it anywhere. Can anyone help?