INSERT Statement Conflicted With COLUMN FOREIGN KEY SAME TABLE Constraint

For some reason, I'm getting this error, even without the DBCC Check:

INSERT statement conflicted with COLUMN FOREIGN KEY SAME TABLE constraint 'Category_Category_FK1'. The conflict occurred in database 'mydb', table 'Category', column 'CategoryID'.
The statement has been terminated.

The very first insert fails...it was working fine before:


DELETE Category;

-- Now, insert the initial 'All' Root Record

INSERT INTO Category
(ParentCategoryID, [Name], [Description], DisplayOrder, DisplayInExplorer, Keywords, Active, CreateDate, CreateUserID, UpdateDate, UpdateUserID )
SELECT 1, CategoryName, '', 1, 1, '', 1, GETDATE(), 1, GETDATE(), 1 FROM CategoriesStaging WHERE CategoryName = 'All'

INSERT INTO Category
(ParentCategoryID, [Name], [Description], DisplayOrder, DisplayInExplorer, Keywords, Active, CreateDate, CreateUserID, UpdateDate, UpdateUserID )
SELECT 2, CategoryName, '', 1, 1, '', 1, GETDATE(), 1, GETDATE(), 1 FROM CategoriesStaging WHERE CategoryName = 'Store'


/* Finally, insert the rest and match on the Parent
Category Name based on the CategoryStaging table
*/

WHILE (@@ROWCOUNT <> 0)
BEGIN
INSERT INTO Category
(ParentCategoryID, [Name], [Description], DisplayOrder, DisplayInExplorer, Keywords, Active, CreateDate, CreateUserID, UpdateDate, UpdateUserID)
SELECT c.CategoryID, s.CategoryName, '', 1, 1, '', 1, GETDATE(), 1, GETDATE(), 1
FROM Category c INNER JOIN CategoriesStaging s ON c.[Name] = s.ParentCategoryName
WHERE NOT EXISTS (SELECT 1 FROM Category c WHERE s.[CategoryName] = c.[Name])
AND s.CategoryName <> 'All'


Here's the schema:

CREATE TABLE [dbo].[Category](
[CategoryID] [int] IDENTITY(1,1) NOT NULL,
[ParentCategoryID] [int] NULL,
[Name] [nvarchar](255) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,

CONSTRAINT [Category_PK] PRIMARY KEY CLUSTERED
(
[CategoryID] ASC
) ON [PRIMARY]
) ON [PRIMARY]

GO
USE [mydatabase]
GO
ALTER TABLE [dbo].[Category] WITH NOCHECK ADD CONSTRAINT [Category_Category_FK1] FOREIGN KEY([ParentCategoryID])
REFERENCES [dbo].[Category] ([CategoryID])