This started after a restore of my Mac from a Time Machine backup to a completely new machine.
The Catalog shows all my images and the correct edits, but if you right click the folders within Lightroom and click Synchronize Lightroom tells you that all the files need to be deleted and re-imported.
I tried updating the location of the images, without success.
I eventually exported the entire folder structure as a new catalog, which worked, but I lost all my publish settings in the process.
After a while though the new catalog went out of sync as well.