My problem seem to have happended after migration from Joomla 1.0.x.
It works with SEF ON
My solution was the following:
Open the toplevel menuitems with submenuitems in them. "Change" the menu item type to the same as before. Also I had to make sure that there was not used a - in the alias.
If need you could change to a completly different menu item type and change it back.
I did not change the module settings so that submenu is shown all the time.
My site was:
Joomla 1.5.25 (same error at 1.5.22)
Menu type: Legasy - Vertical
SEF: Yes (and keept on!)