I figured this issue out the problem was in the name of the mailbox. The name contained a "space" so it was failing on exchange since there isn't any spaces in email addresses. Thanks for the help!
Example:
Bad mailbox name: Bob Marley,VM
Good mailbox name: BobMarley,VM
Hope this helps someone in the future.