If you just go to WP-admin- Post- Categories and change the slug it will work but then you have a duplicate content problem on the same domain.
There are many issues like this unsloved in the wordpress support forum.
I searched a lot and then found this: Editing and Organizing WordPress Category Slugs | Ridhuan's Blog
I guess this is the only thing you can do.
I am sure there will be an .htaccess way to, I have just mailed one of my friends about this. He hould reply in the evening.