Please check your browser's Javascript console for errors immediately after successfully deleting a category, and on the next few requests. You can also try your PHP error logs. Look for errors occurring during a request to wiki_ajax.php?c=deferred which is the actual workhorse for deleted content.
I cannot duplicate the issue here, so I suspect it's a Javascript issue, although there may be a PHP conflict as well. One time I thought I duplicated it, but it was really I saved it to a different area and didn't delete it first. When I deleted it, I didn't get the error. Please let me know your findings.