Eh, the Windows Vista/7 Start menu came with good changes and bad changes.
The search feature is definitely a boon, but I don't feel it's panacea. If you just want to browse the software on somebody's computer, or if you forgot the name of the program you want to run, the search feature is no help.
The really bad decision they made was to remove popout menus from the Start menu and replace them with a scrollbar. This definitely made the Start menu less usable, and I feel Microsoft's only reason for doing it was for aesthetics.
The real shame is that there was never an option to have both the search feature and the popout menus. It was always one or the other.
But the search feature is nice, because the Start menu has never been well organized, and the new Start screen is no improvement. But does it have to be this way? Linux distros have well-organized start menus. I feel like Microsoft could have made an effort to create a framework that would have fostered a well-organized menu, and we could have had the best of both worlds.
But obviously we don't live in a world where that happened, so we just type our commands into a search box. It works, but at this point we may as well be running our programs from a terminal.