in ontological structure - they already have the category tree. It's
for the casual user to type in a few words they're thinking of. Think
something like Getty Images. "Commons is sorta like Getty Images
except it's all free and the search sucks."

And why not work on metadata? If you have possibility of inserting keywords this will improve information retrieval.
Now we have the technical metadata, we need more metadata on the document,
we definitely need to improve the descriptive metadata of the represented object.
For example, if I have a scan of a public domain book I need both to describe the scan itself
and the book.
If we would have the possibility of using the Keywords in the DC as tags, in a user-friendly way,
we could have both old categories and tags useful for searching.
It always go in the direction of Dublin Core (I bet this a recurring discussion too...), and it solves problem of Wikisources too (I'm sorry I repeat myself, but I a cause worth of it ;-))

Aubrey