Rob,
Check your licensing. CUE has a limit as to the maximum # of users who can be assigned mailboxes.
One more possibilty - assuming you have adequate licenses, reduce the mailbox sizes of individual users & see if that frees up enough space. CUE modules have very limited storage space.
Hope this helps.