How to sort category by path and sort order?
The problem is you need to extract the sort order for the root items and make that same order apply to the sub-items in the tree without re-ordering the sub-items.  In Oracle you can do this with a windowing function as follows:

SELECT RPAD('- ',Length(Path)-1,'- ') || label, levelx, path, sort_order
   , min(sort_order) OVER (PARTITION BY FirstLevel) Sort_Order2
FROM (
   SELECT id, parent_id, label, levelx, path, sort_order
      , substr(path,2,1) FirstLevel 
   FROM t1 WHERE Label IS NOT NULL
)
ORDER BY Sort_Order2, Path;


I don't know if you can do something like that in MYSQL, so here is a version using a GROUP BY and self join that works in MySQL 5.5.28.

SELECT Label
FROM T1 a
JOIN
   (SELECT SUBSTR(Path,2,1) FirstLevel, MIN(Sort_Order) FirstSort FROM T1 
      WHERE Label IS NOT NULL GROUP BY SUBSTR(Path,2,1)) b
   ON substr(a.Path,2,1) = b.FirstLevel
ORDER BY FirstSort, Path;


(SQL Fiddle)