Try these steps:
1) Re-inventory the tape containing the data.
2) Go to tools options and click on the catalog tab and uncheck the box use "storage media based catalogs".
3)Now, Try cataloging again.
This will take longer time to catalog when compared to "storage media catalog" because it will catalog the tape byte by byte.
4) Now, run the restore.
If it dosent work,Install the latest driver:
Install the latest veritas driver from following link:
VERITAS Backup Exec (tm) 9.1 - Device Driver Installer (20041101) - Includes Tape Driver Release (20041006) and Robotic Library Release (45) (Intel Only)
http://support.veritas.com/docs/273853
Go to the devices tab in backupexec , right click on the device and go to properties and check for the statistics:Any Hard read/write errors.