Thanks for the post Ken.
LEO permits you to add an additional library/changer to BEX by allowing another device to have drives. So, while my primary library has 2 drives, it doesn't require an LEO license. However, because I still use our older DLTIV changer to run restore jobs, it requires an LEO to run jobs. Apparently, if I add another changer (e.g. our older DAT changer), I would either need to buy a new license or disable one of the other two devices already online.
Now, for the problem. Shilpa, your post wasn't helpful. Ken, your post was partly helpful, but I ended up contacting Veritas support. The issue was related to the entries for the changers/libraries in the BEX database. (This also solved another related issue where older tapes would show up as 'Cleaning Media' or simply not be recognized by the changers. I would have to recatalog each tape to overcome the problem.)
To resolve the issue, I disabled and then removed the drives and changers from the Device tab. I then stopped and restarted the services. After this, I ran the device configuration wizard, installed Veritas drivers again, and then configured the drives and changers. Once I was finished, I again stopped/started the services. This fixed the issue and allowed all three drives to run jobs simultaneously.
The lesson here is that the BEX database controls alot more than I had realized. Once I fixed the devices, the problems with the tapes (being changed to cleaning media or not used for a restore even though the tape was imported by BEX) was resolved.
In summary: the solution is to remove your changers and drives and then add them back again.