Problem with “The category you are trying to create already exists.”

I’m using WordPress 2.5.

This is what I do before I get this problem.

I edit my category hierarchy to became like this.

All(Parent)
-Categori A(Child of All)
-Category A1(Child of A, 2nd Generation Child)
-Category B(Child of All)
-Category B1 (Child of B, 2nd Generation Child)

What I’m trying to to is when we click Category All in the webpage, it list all the post in my website. But I found out it’s not working.

So I go to my wp-admin page,
Manage,
Categories,
Select the “All” category and click delete.

To my surprise it also delete the child category and the second generation child category.

So I said “It’s okay, I add it again.”

But when I try to re-add the category, it said that “The category you are trying to create already exists.”

But my God!
The category is not even listed/visible in the categories table in the wp-admin page.
Some help is appriciated.