So after crawling through forums I found a solution. The issue is to do with stray nodes.
Run this script and all your problems go away:
DELETE FROM umbracoNode
WHERE
(
id IN
(
SELECT umbracoNode_1.id
FROM umbracoNode AS umbracoNode_1 CROSS JOIN cmsContent
WHERE (umbracoNode_1.nodeObjectType = 'C66BA18E-EAF3-4CFF-8A22-41B16D66A972'
)
AND
(
umbracoNode_1.id NOT IN
(
SELECT nodeId
FROM cmsContent AS cmsContent_1
)
)
)
)
Update:
If that doesnt work you can also try this: