Good morning Mark,
Yes, you can restore data from a tape that was written to in another version of Backup Exec as well as another Media Server.
The error that you are receiving can indicate a couple of things.
Have you run an inventory on all of the media in the media set?
If you do not have all of the media, you can get around this error by going into tools - options
Select Catalog on the left side and deselect "Use Storage media based catalogs" and "Request all media in the sequence for catalog operations."
This will take longer to catalog but it will read all of the data on the tape you wish to restore from.