I think a script may be your best solution here. Have it look up the catalog number in the 2nd table and then reference back to the first and update the FKID based on what it finds. Then when it's done that, you can reconfigure your relationship to use the pkID <-> fkID instead of the Text based Catalog number.
Another option, which might also work for you that I've had to do, is to "retype" the catalog number. Doing a GetAsNumber(CatalogNumber) and that will convert it to a new field as a Number instead of a text. Keep in mind that won't work if the catalog number has anything other than numbers in it.
I'm sure others may have a better solution, but that's my input on it.
The key thing is to assign the new correct value to your FK fields before you make a change that breaks the current relationship. That may require setting up a temporary additional table occurrence of your parent record and even a field to hold the new primary key that is separate from the original catalog number field.