Chris,
First off the forums are Peer to Peer only. Symantec employees will post from time to time when we are available to do so. If you need imediate support please contact us using one of the ways listed in the following link.
http://www.symantec.com/enterprise/support/contact_techsupp.jsp?pid=15047
But as for your issue, here are a couple things to try.
1. Turn off Use Storage Based Media. (Tools - Options - Catalog)
2. Stop all the Backup Exec services, rename the catalogs folder (default location is in the install directory) to catalogs.old. Start the services back up, re-catalog the media you wish to restore from then attempt your restore.
3. Also, are you running a verify on the backup jobs?