I haven't seen this behavior before. Can you try removing the product from the category without adding any subcategories first and see if that works? You can set the product to have no categories by clicking on the categories while holding ctrl (on pc) or command (on mac). Check to see if the product shows up in the category or not.
The next thing to check would be to go into the database and check the ps3_productcategories table. Do a search on the ProductID of the product you're changing the category for (you can find this in the ps3_products table). Then you would get a list of the Ids of the categories that the product is added to. You can check which categories these are by looking in the ps3_categories table. This way you can check if the product is added to the undesired category. A workaround to this issue would be to remove that entry from the ps3_productcategories table and it won't show up in that category anymore.
