Originally Posted by SpatiallyAware
Alright I believe I've got it.. somewhat.. figured out. You have to click on 'songs' (versus 'albums') on the new top bar.
Search is still broken, but at least I have a manageable way to sort things.
In iTunes, if you are looking at the search bar, you should see a little down triangle on the magnifying glass. Click that, and then make sure that 'Search Entire Library' is unchecked, that should make it search the old way, where it excludes items as you type.