Searching in iTunes 11 no longer filters column browser options?
To get the desired effect you can click on the "magnifying glass" icon and deselect "Search Entire Library". This prevents the Miniplayer version of the search and filters both your Column Browser and the list of songs (or artists/albums/genre).