Call me old-fashioned but I liked this way better. Search-based interfaces don't help when you know what you want to do but don't know what applications are available to do it. On Ubuntu for people coming from other OS's, this is probably a very common experience (e.g., "I want to listen to music, what media programs are on this OS?"). I like being able to get on an Ubuntu box and riffle through the hierarchical application menu to see what's installed and what I might need to add for my own use. The fact that the hierarchy is well-integrated with the package manager makes it all the more worthwhile.
By moving away from this format in e.g. Mac OS X, I have a hard time keeping track of what applications I have installed without riffling through my entire Applications folder from time to time. Unless you put your Applications folder as a stack on your dock (which is not the default), I have no idea how typical users on Mac OS X remember and launch apps that aren't pinned to their docks.