Long time lurker, first time poster; found this thread via a Google search and as I think I just figured out a possible solution, thought I'd share.
I was seeing the same thing on our Moodle install, version 2.4 (with some local customizations): the "My courses" showed all our categories ("Fall", "Spring", etc.) and then showed all courses within each category (rather than just the courses the teacher or student are enrolled in), and the "Courses" subtree showed all categories with all courses (as expected).
I believe the following solved it:
Under "Site Administration" --> "Appearance" --> "Navigation", I enabled the settings for "Show all courses" and "Show course categories" and then disabled "Show my course categories".
My thinking is that maybe having two copies of each course category on the page is the source of the problem; maybe they both have the same underlying ID on the navigation tree, and so when the second copy of a given course category (under the "Courses" subtree) comes along, it would be overriding the first copy of the course category (the one under the "My courses" subtree) - if so, it would make sense that disabling the "Show my course categories" would solve the problem since you'd then only have one instance of each course category on the page and there wouldn't be anything overwriting. (Hopefully that made sense!)
I've looked at the PHP code for the navigation section (/lib/navigationlib.php), but was unable to find a way to fix this via code so that it would do what I expect it is meant to and allow course categories to show up both "My Courses" and "Courses"... but the work-around is good enough for me for now. Maybe someone more familar with the Navigation library can figure it out.
Erin