In Moodle 2.0.3 the navigation tree algorithm is flawed. In all cases where the 'sortorder' field has been variously changed from the default 999 by moving categories around, subcategories are likely to precede their parent categories in the $categories array, thus forcing an error:
Warning: array_key_exists() expects parameter 2 to be array, null given in .../moodle/lib/navigationlib.php on line 1298
...and losing all the sub-categories located above the parent in that array!!
...and preventing navigation operating correctly on remaining sub-categories!

Debugging on. Any case where a sub-category has a lower 'sortorder' value than its parent (which will of course have a lower 'depth' value)!
But without debugging on you can still see the fault in the resultant tree.