Update: Got LR syncing working again!
Solution:
LR wasn't updating to the latest version either through the in-app Help menu or via the CC desktop app - it thought it was already the latest version. I updated LR and synced started working.
(how to check your version of LR: Keep your Lightroom version up to date )
Steps:
1. Delete the OPM.db file (instructions: Available updates not listed for Adobe Creative Cloud applications )
2. Uninstall LR via the CC desktop app
3. Reinstall LR via the CC desktop app
It's disgraceful that I've had so many issues with the CC desktop app not installing products correctly, not updating correctly, not syncing files correctly, etc, etc, and Adobe just keep releasing buggy software that wastes hours/days of our time and they don't seem to care at all. Already well on the road to switching everything away from Adobe - and I've been using them for at least 15 years and am an adobe certified expert. Shame on you Adobe for charging huge subscriptions for software that doesn't work.