There is a bug whereby categories appear not to be added to the navigation structure when a course is added with the same path as a category.

Don't know how I missed this one, either way I will commit a patch to resolve this after some more testing.
The patch itself combines the desired key (internally this is the structure id) with the type internally to ensure that any two elements of different types with the same id's and paths can coexist in the same point of the structure.