Ok I found the issue, Or at least half of it.
The problem was that I was trying to delete a folder referring to another shared folder.
In the Shared Folders gui, both folders were marked as not referenced.
Simply put: deleting folder B before folder A worked ok, and allowed me to delete folder A.
Now I can also create more new folders, which was prevented before - this part I did not understand the reason for: must be somehow related to the previous situation but...?