Unable to catalog old media

I have 3 tapes that I need to restore data from.  I can get them to inventory and catalog without error, but when I the restore data option I get this error: "the selected media was not found in the catalogs. You must first catalog the media if you want to use it for restore options."  I searched some of the forums, but I feel that searching for cataloging media will give me other errors and searching for "cataloging media that has been cataloged" won't work to find a solution. 

The server I have setup now is a new server.  The old one was formatted.  I am running an eval version of 11d until I get our license...

The media shows up in imported media>backup exec and windows nt backup media

Thanks for you help