Exchange has got loads of issue when it comes it making it work with Mac OS. I created and account a month ago and had to rename it. Although after the rename of the account the user was able to login to the windows client and also use outlook and OWA to login and use email but when the same user tried to login using Mail on Mac it did not work for him. Mac Mail was giving authentication error, on investigating a bit further I came to realise that it was a server issue rather then a client issue.
It turns out the on account rename the alias for the mail account was not changed, so the login name and he alias name for mail account was different, on making them similar I was able to login using Mac Mail. This practice took me almost 3 hours to sort this issue out, so I decided to blog this for any other unfortunate ones who bump into this issue. I am just glad that I did not try to back the mail account and delete and recreate it, that would have taken me almost a day to go through all of that.