I decided to clean out some older users I have on my Cyrus IMAP server. The documentation says to do e.g.
> sam user.foo cyradm d > dm user.foo
This however did not work for me, even though the "d" flag is what the docs says. Searching the Cyrus forums, I found out that the permission for the admin user has to be set to "c" for the user / folder to delete. So I did
> sam user.foo cyradm cd > dm user.foo
And things works fine agin.