I don't know about anyone else, but as my app collection grows, I'm finding it harder to justify having a single category (say, Utilities) without some means of sorting or filtering it. I don't think the problem can be solved properly by allowing the user to add categories beyond the handful that is now there. From what I have gathered from perusing the forums, it seems nesting won't be on the PA roadmap for the foreseeable future.
So what about having a tagging system within the menu's search? The tagging could happen either by right-clicking, opening it's own window, or within the Rename window. This would allow the change (if it happens) to be otherwise concealed from people who are familiar with the current layout and who don't care/need to use tags. However it gets done, I think it's imperative to at least have some way of organising beyond what is now in place.
Currently I've resorted to renaming each app with the "tag" I think appropriate in front of it in parenthesis - but this is an ugly, unnecessary workaround to an easily rectified problem.
Edit: Since I'm on the topic of improvements to the menu, I'd also like to suggest adding a hotkey that can show/hide the menu without having to click either on the taskbar or notification area. Perhaps not very important, but convenient.