I was not able to reproduce the issue.
I created a category "main" and a sub category "sub" and then i tried to add a main category "main" and i got the message as you explained. So i deleted sub category "sub" and i was able to add "sub" as a main category.
Did my steps follow your steps or am i missing something here?