Please verify if the exact make and model of the storage device is listed in the HCL(Hardware Compatibility List) from the following link:
http://support.veritas.com/docs/271383
If the drive is listed in Veritas HCL, then verify whether Veritas drivers are installed. Drivers other than Veritas driver may not work properly with Backup Exec.
Run "c:\Program Files\VERITAS\Backup Exec\NT\tapeinst.exe" and select "Use VERITAS tape drivers for all tape devices" option. This will install Veritas tape drivers. You may download latest Veritas drivers from the following URL:
http://support.veritas.com/docs/273853
Perform the following steps to resolve this problem:
1. Open Backup Exec
2. Go to Devices tab > Right click on the tape drive > uncheck "Enabled"
3. Again right click on the tape drive and select "Delete"
4. Stop all Backup Exec services
5. Start all Backup Exec services, and verify if the tape device is detected.
6. Create a new backup job, run it and verify the results.
Hope this helps.