If you have a very large contentstructure, this should be used carefully. If eZ attempts to display too many nodes, the page load time may exceed the server's allowances.
If the TreeMenu settings are at their maximum, you won't be able to expand beyond them.
The two treemenu settings I mentioned - maxdepth and maxnodes limit the content displayed in the contentstructuremenu. If the menu is displaying the maxdepth --or-- maxnodes, you will not be able to expand it further.
You might want to check those settings.
With respect to the AJAX note - I think AJAX has great potential with eZ publish. By allowing HTML (AJAX) pages to handle the visual interface and using eZ to deliver content with a transparent background you can integrate eZ content into sophisticated designs developed with visual layout tools such as DreamWeaver and HomeSite. I'm not sure how it would work with the search engines, but it is probably worth exploring.
I got this problem once.
I think I had to reinstall the nav menu (I use the ajax treemenu witch speeds up things a bit) http://ez.no/community/contribs/hacks/ajax_treemenu_on_demand_tree_menu
and I also think I did a cache cleaning. why don't you upgrade to 3.7.4 while you're at it, it fixes a lot of small bugs in 3.7.3