If you're restoring from tape, you might run into hassles, and you have to stage to disk instead. The default path is C:\Temp, and depending on your C:\ partition size, and the size of your Exchange IS, you will run into problems.
I take it you're successfully backing up to tape?
Try this and see if it works...
https://www-secure.symantec.com/connect/articles/restoring-exchange-or-individual-mailboxesitems-using-backup-exec-howto
If it doesn't work, then I'd suggest logging a call with Symantec. Logging the call depends on which country you are in, and you can find that out here:
http://www.symantec.com/business/support/assistance_care.jsp