I just released a plugin that does exactly this. Let me know what you think.
http://wordpress.org/extend/plugins/media-categories-2/
While I think this might be something that should remain pluggable, I think there are some minor changes in core that could be made to make it easier to switch this sort of feature on, without _needing_ to resort to writing a custom walker and a custom metabox.
There is a built in ability for a developer to add taxonomy support to media, but the interface just ends up being a simple text field that users would need to type slugs or category names into directly. As a result to make this look half decent developers need to jump through a couple hoops. This should be simplified, and turning on taxonomy support for attachments should result in a clean usable interface by default.