First, which version of Backup Exec are you running? Help > About, and look for the 4-digit revision number ... Rev.7170 is the most current and is available via this link.
http://esdownload.symantec.com/akdlm/CD/MTV/BEWS_11D.7170_32BIT_VERSION.zip
Second, the Backup Exec interface communicates via the remote agent with the resource being backed up or restored to, even on the media server.
Your message is somewhat confusing, but let me start by providing a link that references the error you identified ... and thank you for including the hex code, that made finding this document a snap.
http://support.veritas.com/docs/280668
Bear in mind that this problem can be caused by several issues and therefore has not one solution, but many, and you may need to call in to explore this completely. That said, because of the variety of possibilities, I can only provide a few common solutions in this forum.
A common problem tends to be authentication. The following are requirements for the Backup Exec service account: Domain Administrator and a member of the local Administrator's group; for Exchange purposes, the account must be an Exchange Full Administrator, be activated, email enabled, not hidden from the gallery, AND have sent/received email to the account. Within Backup Exec, under Network > Logon Accounts, the account should not be restricted.
Try simply recreating your restore job; then review the selection in the View Selection Details tab before beginning the restore.
