Hello Linda,
Well you can backup the catalog folder itself using the Backup Exec.
Another thing > there is no use of restoring the BEDB.BAK file because it contains the backup of the database which is the data folder so you wont get your catalogs back even after that ( What will happen is that you will loose your new job configuration made after the backup was taken ) so please do not restore the BEDB.BAK file.
I havent heard of a situation where BEutility would wipe out a catalog folder when changing paths. I would presume you didnt perform the steps correctly.
In any case you can only re-catalog your tapes now and in future make sure you have a copy of the catalog folder.
Thanks,
ANevatia