I have been facing this issue since past few days, and Salesforce support takes forever to fix this although I created a ticket. I have an open priority ticket open since 3 days now.
Although from the answer shown here('Contacts Registration Failed' Marketing Cloud Connect error), it should be a standard release fix.
The issue happened because a sync which was paused and restarted a sync.
Is there a standard way or hack to delink and sync the object again by myself?