Does the user have a mailbox?
did you run the preinstaller on the exchange server?
go to full mailbox access in EMC and remove the service account and re-add it and try again please.
It is unable to log into the mailbox to create the relationship for that user. Is the user hidden from the GAL?