I never had to do anything to get the All Programs soft key to work.
I just ran a game that was located in a subfolder of the programs folder and the All Programs key still works perfectly.
Seems like a lot of these weird problems only affect a few people.
