David, so this was all working, then you applied the patches and it stopped working? Or did it never work?
Also, when you change your tapes, are you removing the entire tray, or are you using the mail slot?
I had a problem with people over-riding the backupexec device lock on the tabe library, and then it would no longer respond to backupexec.
Try manually running the 'unlock' and 'lock' on backupexec and see if you have any success.
Cheers.