Currently, WordPress category and tag slugs are (severely) limited because they are all stored in wp_terms. Because of this, the blog I maintain had several category names with -2 attached at the end because a tag with the same name already existed (despite the fact that the URLs would not be the same). This is, ofcourse, not very clean and because there is no way to give each tag/category its own custom URL, I had to change the tag slug manually to be able to give the category that specific, clean, slug.
I find it very frustrating to have such limitations when it comes to tag and category slugs; you would think that by now it wouldn't be depending on just one database table.
So what I'd like to suggest: get rid of the wp_terms table/revamp it, or add the ability to have category slugs and tag slugs coexist by allowing custom URLs for each category and tag.