Make a backup with a new name and try running Check/Repair 3 times to see if it has really fixed the error. If so, the problem is solved.
If the error remains unfixed, you can try exporting everything to a gedcom, create a new PAF file with a new name and import the gedcom. Then check in File > Properties to see if the new file has the same number of records as the old one. If it has, the problem should be solved.
Another possibility is to take the file on a flash drive to your closest Family History Center, and open the file in PAF Insight or Family Insight. This should automatically create a new name tree. Save the file from Insight with a new name. Exit Insight and open the new file in PAF and run Check/Repair. It should report no problems with the name tree now.