Re: so... kde3.5 was dumped for kde4 why again?
The default one (which has tabs), which is new compared to the kde 3.5 one, is called "kickoff". Lancelot is newer still, it just had its first stable released a week or two ago and almost certainly isn't installed by default on your system. For me at least it is better than both the KDE 3.5 menu and the default kickoff-style menu. It seems to combine the best features of the traditional and kickoff menus while adding some cool new features.
For instance each section has a heading. There is nothing new there. But what is new is that you can drag that heading to the desktop to add a plasma applet with the contents of that heading. So for instance you can make a "favorites" applet on your desktop. You can do that several times, making several separate plasma applets or a single applet with multiple items (depending on whether you drop additional items on a blank space or on an existing lancelot applet). So I have one applet with my favorites and my "system" section and a second applet with my places and my removable devices (which disappears when there are no removable devices and reappears when one is connected).
Lancelot also has a good (optional) no-click interface and (finally) the option to choose the icon I want to use for the button. I would definitely check it out. Make sure you play with the options a bit once you set it up. If it is available it will be a package with the word "lancelot" in it. It is not completely finished yet but it already does everything the other two menus can do and far more. In my opinion lancelot is one of the first programs that is really beginning to show what KDE4 is capable. Up to this point they have been largely just trying to get things working as well as they have in the past, while lancelot finally beings to branch of into new territory.
I am still waiting for the Raptor menu which looks better yet, but there doesn't appear to have been much work on it lately so who knows when (or if) it will be released.