If you are still having problems, we are having what sounds to be almost the exact same problem...and you really need the data back there is a product called "recovery manager for Exchange" that might be useful. With the eval verision I am able to successfully catalog the problem tape, and see mailboxes with in the database...we have not decided to buy it yet, as we have an open case with symantec to resolve this...
I'm still waiting to hear back from Tech support as to how to resolve this issue, our story goes like this...backup performed on another backup server using backup exec, that is no longer available, on an LTO tape, we needed to restore the Exchange server, we tried cataloging the tape on our server (backup exec), the catalog says it completes successfully, but the byte count is 64bytes, yet I know the store I'm after is 22GB, and when I try (just in case) to restore it errors out..in the restore selection list, it shows the database, but no details...yet if I look at the properites of the tape, it says about 24GB have been used....
hope this helps you out...if Tech support finds a solution I'll post it here....