INSERT statement conflicted with COLUMN FOREIGN KEY SAME TABLE constraint

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]