Looking at the announcement on the main page, and also looking the way SKINBASE.org is set up, why aren't the themes displayed like any other category?
That is, why not show thumbnails of each theme, along with a Zoom option, and allow you to select your theme that way, rather than the trial and error approach now?
As more themes are added to the site, selecting them by name only will become even more of a problem.
It might even be cool to allow comments for each theme. I'm sure theme authors would enjoying reading about what people think of their themes.
