How can I fix this permalink problem?

I decided to change couple of my category names on my new site to something more descriptive. So one category, for example, was named "water" and I changes it to "water purification". And it does now show up as "water purification on the side of my page, but, when you click on that category, it's still showing the old category name - "water" in the permalink. Why would it do that?

When you go into "categories" in the dashboard, it is showing the new categories that I created. I have also gone into each article post and unchecked them form the old category name and checked the new category name.

Also, if you go into Appearance > Menus, you can see the new category names are there too. So, why does it still show the old category name in the permalink of that category? It makes no sense - am I missing something?

After switching my post from "water" to "water purification", I deleted the category "water" to see if it would fix the problem. But, instead it created another problem - when you click on "water purification" category on the side of my page, it now takes you to a 404 -file not found page.