Some developers are working on a neat new program menu for KDE called Raptor Menu.  Thanks to Plasma and other underlying KDE 4 technologies it is now a pretty trivial hack to change the program menu if you don’t like the default.  Such enhancements exist for KDE 3, but they are all very kludgey.  Thanks to Plasma’s modular nature, it’s easy to replace it.  Even the KDE developers have acknowledged this when people have complained about their new program menu.  Bear with them to fix it, they say, but if you don’t like it, it’s now very easy to implement your own.