Created a new mailbox database in the same storage group as the existing mailbox database
moved some users mailbox's to the new database.
now they can no longer access their voicemail
"your messages are not available"
I restarted Exchange and I restarted Unity... still no access for them.