So here's what I've come up with:
It pulls audio entries from Zeitgeist to populate the sections, so needs the Banshee Zeitgeist Dataprovider extension to be installed and active for it to find any results. It will also only find results of music which has been played while the Zeitgeist extension was active, so music which has not been played will not show up. There are 3 sections: Recently played, Most played and Ever played (I had to use that terminology since it won't have all the music initially). The recently played section lists the last 100 songs played, the Most played lists the 100 most played songs and Ever Played lists all songs ever played, sorted from first played to most recently played. Searching will narrow down these lists. Clicking on any of the entries (or pressing enter on them) plays them through the default player for that file type (which may not necessarily be Banshee!).
If music has been played in a program other than banshee, the Zeitgeist entry may not contain all the information to show the artist and title, so it falls back to showing the file name. It also won't be able to find the album art, so it falls back to a generic music icon. There's also an issue where if the song in Banshee has a different album artist to the track artist, it won't find the album art either, so it uses a generic icon again.
If anyone wants to try out this lens (and see if it actually works anywhere else besides my own computer), I've uploaded the code to launchpad.net at: https://code.launchpad.net/~markjtully/+junk/unity-music-lens. There's a readme file there which gives instructions on how to try it out.
Opinions and comment (and bug reports!) are welcome.