Back in mid-August I resuscitated the F-Spot query branch, fixed some things, and added some new features. In particular, I added a type-to-find bar where you can enter arbitrary and/or boolean queries (using parenthesis as needed). The not operator is not supported yet, but shouldn't be hard.
I also created an animated GIF of the type-to-find bar in action.
More recently I changed the menu options - in the context menus and the Find menu. They are now more functional yet simpler.
Larry says he wants to get this in soon. You can follow along at home by CC'ing yourself to the infamous bug.