I often find myself using the search bar in windows since I'm so used to linux's ability to run anything from anywhere. All binaries are in 1 place, so I can easily call upon applications where I know what they're called.
But for people used to windows, or just people looking to find a seldom-used but still needed application, I could see the annoyance. Though Windows's Vendor->Product organization was always pretty disgusting compared to Category->Application organization.
EDIT: Ninja'd. In response to the 2D plane argument, I could see that, but I think the problem people are finding is the icons aren't "iconic" enough. If the design of things was a bit simpler and just had like, a picture of a calculator and the word "Calculator" or a picture of the Quake logo and the word "Quake" or something... kind of like how icons in everything has been since pretty much ever, there'd be no problems. A lot of touch interfaces pretty much extend the well-known "icon with descriptive text" to making the icons larger, and that seems to work fantastic. I think the general complaint should be that the Metro UI is really fairly "busy", with lots of complex patterns and poor contrast between colors, and little animating googaws, making the scanning process impractical. They've replaced the standard Windows desktop unnecessarily.
____________________