This is often caused by damage to the product category table.

The following query checks for any category where the level does not match the actual level as given by the path…
SELECT path, level, (SELECT LENGTH(path)-LENGTH(REPLACE(path,'/','')) AS tmp1 FROM (SELECT * FROM catalog_category_entity) AS table1 WHERE catalog_category_entity.entity_id = table1.entity_id) as actuallevel FROM catalog_category_entity having actuallevel != level

Fixed by the following update query:
UPDATE catalog_category_entity SET level = (SELECT LENGTH(path)-LENGTH(REPLACE(path,'/','')) AS tmpl FROM (SELECT * FROM catalog_category_entity) AS table1 WHERE catalog_category_entity.entity_id = table1.entity_id);

The following query checks for any category where children_count does not match the number of actual children found:
select path, children_count, (SELECT COUNT(*) FROM (SELECT * FROM catalog_category_entity) AS table2 WHERE path LIKE CONCAT(catalog_category_entity.path,"/%")) as actualchildren_count FROM catalog_category_entity having children_count != actualchildren_count;

Fixed by the following update query:
UPDATE catalog_category_entity SET children_count = (SELECT COUNT(*) FROM (SELECT * FROM catalog_category_entity) AS table2 WHERE path LIKE CONCAT(catalog_category_entity.path,"/%"));

Both these problems can be fixed by running the corresponding fix query from the reference below – but I’d prefer to check if a problem exists before running a potential fix.

References:
Guide to running queries to fix this problem (but not check if it ever existed)