Keep the things above in mind, as well as:
You will not be doing a restore of the exchange backup, you will be doing a redirected restore of the exchange backup. When you create the restore job, be sure to select the Exchange Redirection node and give the appropriate information.
Your new test exchange must match EXACTLY the original one. All folder sturctures and names must be identical. If you have three storage groups, each with four mailbox stores on your orignal one, then you test one must have three storage groups, with four mailbox stores in each with the exact same names on each level.
Don't have a recovery storage group involved. Don't even have it partially created. RSG are good for what they do, but cause issue for everything else.
Make sure you have created, and use, a logon account in Backup Exec which has full rights to the new domain and exchange server.