As of this spring some time, my WP-installation all of a sudden didn't output what was specified in the Page Menu Label fields.
I then realized I have add the Custom Field 'menulabel' on every page, and copy the Page Menu Label into this field.
Does this make sense? I have a few thousand pages to go over, so it would be great if you could prove me wrong :)
Regards
Hans Magnus