RESOLUTION:
In all my searching I never found a posted solution, well here is what solved my problem...
On the Media Server stop all Backup Exec services. Find your way to the BackupExec program folder, usually found at "C:\Program Files\Veritas\Backup Exec\NT" and change the name of the "Catalog" folder to anything else, I used Catalog1. Then start the BackupExec services again, and BE will create a new Catalog folder. Then Select only the media you will be restoring from and inventory it and then the Catalog should run correctly.
The problem I was having was that my Backup to Disk file names were being re used every few nights so the BE catalogs were 'confused' by the fact that I had different versions of the same file name.