Если до этого категории удалялись напрямую через SQL-запросы (в phpMyAdmin например), то была нарушена сортировка полей ns_left и ns_right в таблице cms_con_{content_type}_cats.
Дальше либо вручную переопределить данные полей ns_left и ns_right, либо сделать импорт БД