Couple of questions:
Did you check these 'relationships' before you started the clean up?
How are you seeing this 'corrupted relationship'? Please provide some details, like what Workspace you are looking in, what Tab, what options?
Take one example, go to the People Workspace, Person Tab, then use the Relationship Button. What do you see? What should you see?
Secondly, please click on Tools, Compact file. Say yes when you are asked about a Back Up.
Were there any Errors when you imported your PAF file into Family Tree Maker?
And, HOW did you import that file into Family Tree Maker as there are options?