If you do a search in the forums, there's a few others that have run into this.
In one, there's a link to an
open bug for it that hasn't been resolved yet.. One thing that was mentioned was that ZCS caches the number of licenses used with a TTL of 1 hour. When the license gets "close" to the limit, it calculates it every minute. I'm not sure how they calculate this. If it's based upon a percentage of license used, then you may not have been "close".
I would try waiting the hour and then if it doesn't, bounce mailboxd (if downtime is a concern). You may also want to open a support case with Zimbra anyway, so it goes on record that another customer hit the issue..