Please reconfirm the following things:
1> the first five character of the account should be unique, example : if you have administrator and you are trying to use admin then it is not unique.
2> should have active mailbox
3> domain admin
4> unhidden from gal
5> should have full delegation.
Also make sure in the BE console click on Network - logon account and you should have the system logon account and you should have the correct credentials for the same.
I hope you are just checking the individual mailbox that you want to restore.
You may also refer to the following document:
http://seer.support.veritas.com/docs/268749.htm
Regards,
Tech29