To change a relationship in an app takes a lot of steps to make sure your data is preserved. In the past I have had the sandbox blow up when doing changes like this and cause me to have to reach out to support to roll back the app. It was done correctly in the sandbox, the transition to production failed in some way on the back end. That was a lot of lost work. Now when doing migrations like this what I do is do it in many many stages.
This can get complicated and is kind of hard to explain fully. This will just be kind of a general idea of what I have done in the past. I always suggest making a copy of your app and doing this in a copy first, perhaps several times.
You need to be careful of losing data here. If you have a lookup field in a relationship and you disconnect that relationship all of your data goes poof from the no longer connected table. So lets say we have a few tables, Companies is connected to Orders based on the Record ID of the Related Company. Then you would have lookups for Company - Name, Company - Contact, etc. When you sever that relationship all the lookups go blank, they do not keep the data that was previously in them.
So when you make a new relationship you need to preserve this data, but only the Related Company or Related Order field really as the rest will flow through the lookup. Basically you need to make sure the right Record ID is still associated with the right Company.
It gets more complicated when switching the relationships to new key fields but it sounds like you may not be doing that. I have probably done nothing but confuse the issue here. It is a hard question to answer without more specific information on what you are doing.
