Are you able to do any media operations like inventory? If you view the available media in the Devices screen in Backup Exec, do they show overwritable and/or appendable for the job type you are running? It may be an odd connection status with the tape library... I would recommend first stopping/starting the Backup Exec services to reconnect with the devices. If that doesn't work, try cold restarting the server and library (if the library is not internal to the server, on restart allow the library to come up and initialize before starting the server). If you are seeing the events mentioned in the previous post, it may indicate a hardware problem.
Russ