Let me see if I have this right. You want to move a "child" category and make it a parent category. Then you want to add the same category again - as a child category? Or you want to switch post categories from one parent to another?
If you have used a category name, then it is in use. If you delete it and want to add it again, you should be able to. Are you saying that WordPress isn't allowing you to add a category name that you've deleted previously? If so, then we'll look into that further.
But as to what you really want to do, we're not clear. WordPress.com currently doesn't offer batch category editing, so you have to edit the posts one by one to change their category, but the Quick Edit feature of WordPress 2.7 definitely speeds up the process so you don't have to wait through multiple page loads.