Thanks for your support guyz. I wanted to inform you that the problem is now Resolved. WE had to Recreate his mailbox and once the replication was complete, the BES server was able to activate the user

Finally after so much of troubleshootings.
I guess the issue was with the legacyExchangeDN as it was not in the proper format maybe because it was not properly migrated from Exchange 2003 to 2007. Even after modifying LegacyExchangeDN, nothing helped. So the final conclusion was to delete and recreate the mailbox only.
Thanks again.