-Check Devices tab in Backup Exec. On right side of screen, is the icon w/BE servername next to it say 'Paused'?
-Try shutting down tape device. Then shut down BE server (cold boot). Then power up the tape device. When the tape device is completely finished initializing and is in a ready state, then power up the Backup Exec server.
-Check into device problems. Best test for device connectivity is an 'Inventory' job on a tape. Backups can fail for all kinds of funky reaons, but an inventory is a simple request for the tape device to read the header on the tape.
Good luck!