Ever though of looking at the logs? if your getting MAPI call failures, reboot the BES and retry adding the using. Expected is that you have the "APPROPRIATE" permissions. Please don't say I can add all users.
Make sure the service account is a part of View only admins in exchange and has Send As, Receive As and Administer information store.
RTFM before complaining