Using the "within" menu next to the search field you can search by add-on category but there is no way to search by theme sub-category. For example, one cannot search for all "compact" themes compatible with a browser version and platform. The theme grid listing does not show a download button and thus there is no way to see ahead of time which ones are actually compatible. You can search for compatibility or list the sub-category, but not both at the same time. A logical solution would be to add a sub-category menu that only shows upon the selection of the themes category. (either next to the main menu or in the advanced tab)
Bug 440811 covers part of this, if not all.
Yes, that might cover the example use case I gave. I would however like the ability to arbitrarily search themes by sub-category for other purposes.
We're graying out incompatible themes now, but I'm wontfixing the sub-category searching.
Actually, no need wontfix, as this was pretty much fixed with the "Refine Results" pane. It allows searching within categories, including theme sub-categories. You can't search from the start by sub-category, but all I really requested was some way to filter by them and this does the job. ;)