Someone else had a similar issue, their solution was this:
Open Active Directory users and computers.
Find the mailbox you want to add the user to, right click, properties, then security tab, advanced button, Permission tab, then at the bottom if the box isn't checked, check the box for "Include inheritable permissions from this objects parent."
Click ok through the warnings, apply, and exit out of those properties and then test again.
Worth a shot.
