I had a problem. I couldn’t change the category slug in some of my categories. So I found the solution at:
http://wordpress.org/support/topic/category-slug-cant-be-updated
The problem comes from the fact that the tags and categories are stored in the same table in the database. And the tags also have slugs. So if there is already a tag with the slug that you want to put in the category you can’t do it until you delete the tag or change it’s slug.
You just need to go to the tags table in the admin panel and change the tag slug that’s making the problem.