I agree, the new start menus are much less streamlined than the older, less stylish versions. It's a real pain when you're looking for something (did they hide the console in System or Utilities?) because every time you go into the wrong folder you have to click the back button to get out, rather than just mousing over the next menu like you could before. For my money the basic menu structure, possibly with a recently used area, is hands down the best layout for start menus. Trying to improve it by complicating things is only going to make it worse.

On the other hand, some of the other stuff in KDE 4 is very promising. I like the ability to embed more than just the Desktop folder on my desktop so I can have frequently used folders always immediately available. The widgets are nice, though a bit lacking in variety at this point. And it does look gorgeous. For my laptop I'm mostly liking it, but it's not ready for my primary desktop where I spend most of my time. I'm still not 100% sure it should be out of beta yet (although 4.1 is a big improvement over 4.0).