Recently while upgrading (import db) CRM deployment from 2016 to v9 we encountered this strange error. After trying everything including mentioned her and running short of time, we opened MS ticket and got a script to run on organisation’s DB, which actually resolved this issue.
Script actually drops foreign key constraints so should be used carefully and at your own risk.

IF OBJECT_ID(‘tempdb..#DropForeignKeysStatement’) IS NOT NULL DROP TABLE #DropForeignKeysStatement

SELECT DropStatement = ‘ALTER TABLE [dbo].[‘ + st.name + ‘] DROP CONSTRAINT [‘ + sfk.name + ‘]’
INTO #DropForeignKeysStatement
FROM sys.foreign_keys sfk
INNER JOIN sys.tables st ON sfk.parent_object_id = st.object_id
AND sfk.schema_id = st.schema_id
WHERE sfk.schema_id = schema_id(‘dbo’)

SELECT DropStatement FROM #DropForeignKeysStatement

DECLARE dropStatementCursor CURSOR FOR
(SELECT DropStatement FROM #DropForeignKeysStatement);

OPEN dropStatementCursor;

DECLARE @currentStatement NVARCHAR(max);

FETCH NEXT FROM dropStatementCursor INTO @currentStatement;

WHILE @@FETCH_STATUS = 0
BEGIN
EXEC sp_executesql @currentStatement;

FETCH NEXT FROM dropStatementCursor INTO @currentStatement;
END

CLOSE dropStatementCursor;
DEALLOCATE dropStatementCursor;

IF OBJECT_ID(‘tempdb..#DropForeignKeysStatement’) IS NOT NULL DROP TABLE #DropForeignKeysStatement