OK - it appears to be data related.

How about making a backup of your data, running the integrity check and selecting Rebuild and then running the integrity check again.

You should make a note to check out anything that is "fixed" during the rebuild process.