"Mailbox already in use" when trying to change Mailbox domain

Hi, I'm trying to change the mailbox domain for one of our users from a secondary email domain to our primary one but I get an unhelpful "Mailbox already in use" error in the Configuration Session. In Web Admin I can change the domain and hit Apply or "Save and Close" without an error but it doesn't actually do anything. As a test I tried changing the domain on a shared mailbox and it worked ok. The only thing I can see which might tie the user to the domain is clients in ActiveSync which I didn't want to delete unless nexcessary.
Is anyone able to advise if I'm looking in the right direction?

Thanks
Chris