I'm a little bit confused here.. Do you mean that "All Programs" is literally not in the Start Menu anywhere? If that's the case it sounds like a registry problem.. Which could be the result of a virus or trojan.. As Davehc asked, which version of Win 7 are you using and did you download it from Microsoft directly?
Incidentally, I have a somewhat similar problem. My Start Menu has programs which have these little black arrows on their right hand side which suggest more menu, but which are unclickable. Not a major impediment, by any stretch of imagination, but just mildly irritating. Ah, I suppose these come with the territory of Release Candidates....
I upgraded from Vista Ultimate 32-bit to Win7 Ultimate 32-bit RC1. My Start menu is completely empty except for the Win7 items (and recently used programs). My All Programs list is empty, even when I install a new program. However, I can type a program name in the search entry and it will be listed in the select list.
I had a heavily customized Start Menu in Vista, which is now totally gone.
If you right-click on the Start button, choose Properties, click the Customize button and if you have selected Display as Menu, you will get these arrow, however, I don't understand why your's wouldn't be working correctly.
Yes, it's gone as you have upgraded you OS, none of the former Vista programs will work. Your OS is now Windows 7, not Vista.
Just for everyone's information, who may be having this problem, I make this post. I had a similar problem after installing Windows 7. I followed the instructions in the fix for which you gave the link (Right Click at All Programs; select OpenAll Users; Etc.). What I found was stray shortcuts -- both in the next folder, and in the Programs folder -- which were obviously not recently active. Simply eliminating those strays allowed all of the program folders to appear in the All Programs Window. All appear as folders, which can then be opened for individual programs. Works real well.