To do any kind of advanced search, the user must create an Automatic Playlist.  There's a couple problems with this:

1) The user must associate "searching" with (automatic) playlists.  This is not very likely and makes the feature much less discoverable.
2) The user must name the search (as a playlist) or it will just be a blank playlist name.

(the first is the primary problem)

It would be great if there was a button on the search bar (a gear icon, or "Advanced" or something) that would bring up a dialog with the same search options.  But instead of "New", it would simply be "Search."

A new source would be automatically created with an appropriate name ("Advanced Search #x" or simply replace the previous "Advanced Search") and selected to view the results.  The user would then have the options to save this search as a dynamic (automatic) playlist (with appropriate name) or modify it/create a new search.  These options could be displayed in a yellow info-bar at the top.