As well as Ken's advice about the Catalog needing emptying you may have to start with an empty Backup Exec Database as well as the database will think the BKF files are in media familes based on the last backup and the same bkf file names will have been in different media familes in October 2009. This mismatch of information can cause a Catalog job to fail.
Basically your easiest way around this is to install Backup Exec to the same patch level on another server (don't run any backup jobs on it so that database does not contain any records of BKF files). Then create an empty Backup to Disk folder then copy in the BKF files you just restored from tape into the backup to disk folder (don't copy the CFG files) then run an inventory and catalog job against the Backup to Disk location.
This sort of issue is why we don't recommend flat file backups of Backup to disk folders - but again as Ken mentioned - the recommended method is to use duplicate jobs within Backup Exec - which has two benfits 1) you should not run into the problem you are having 2) the restore process is direct from tape to the original location holding the users data - you don't have to restore the BKF file first and then run another job to restore the data,