Hi,
This could be any number of things... are the tapes that are in the library overwrite protected by chance? If so, Backup Exec will cycle through the tapes until it locates one that is appendable/overwritable.
If you launch a job and then go to the devices/media tabs can you see the library cycling through the slots, or does it just pick one particular slot every time and start running?
Regards,
Scott