For logging purposes:
The problem is not really solved, but a workaround is to not re-build the menu, but only translate the captions of the menu items.
Further information on the original problem:
The rebuilding of menus work when activated from a standard command button on the menu bar. Performing the same action using a CombBox control results in the problem.