Recent versions of the Cyrus imapd define mailbox ACLs as follows:
c (create)
The user may create new sub-mailboxes of the mailbox, or delete or rename the current mailbox.
d (delete)
The user may store the "Deleted" flag, and perform expunges.
This means to delete a mailbox, you will need to give the user you are connecting with via imap_open() "c" rights on the mailbox in order for imap_deletemailbox() to work. Setting "d" rights for yourself is not the same.
Check the documentation for your version of Cyrus imapd.