Возвращает правильные уровни.Но не уверен, что этот запрос является производительным, это должно быть
WITH CategoryRec AS
(
SELECT Id, Parentid, Name, 1 as [Level]
FROM dbo.Category
where Parentid IS NULL
UNION ALL
SELECT c.Id, c.Parentid, c.Name, (cr.[Level] + 1) as [Level]
FROM Category c INNER JOIN
CategoryRec AS cr ON c.Parentid = cr.Id
),
CategoryRec2 as
(
SELECT Id, Parentid, Name, [Level]
FROM CategoryRec
UNION ALL
SELECT cr.Id, c.Parentid, cr.Name, cr.[Level]
FROM CategoryRec2 AS cr INNER JOIN
CategoryRec AS c ON cr.Parentid = c.Id
WHERE c.Parentid IS NOT NULL
)
SELECT Id, Parentid, Name, [Level]
FROM CategoryRec2