I tried your propositions, nothing change...
Are translations may affect the display? By viewing the contents of the table ezcontentobject_name I saw that the field was sometimes content_translation eng-GB, while all my items are supposed to be in french. Yet in the admin, if I look at the language of objects that don't appear in the tree, the language is french.
Try to add a translation to one missing object to see if it appears.
Then double check how you setup your language settings.
I tried that yesterday, without succes either. Perhaps I have a problem with my installation. But I can't reinstall, there are many datas I wouldn't lose.
I tried to export my content tree to another installation of eZ Publish, but I encounter the same problem.