cannot rename categories / slug name already in use

I was renaming several categories and the first few went fine, but then 3 categories would not change. I would rename them and click save, but then when I went back to the categories page, the categories I had changed still showed as the old names. Finally I deleted them and made new ones, but it forced the slug names to be “slugname-2” it will not let me name the slugs the old slug names – it is saying the slug names are still in use even though I deleted the old categories! How can I fix this?