So it seems to be a general bug rather than something distribution specific.
Looking at the behaviour, it looks a bit like there is a race going on between the code filling out the menu, and the code blitting it to the X server. Opening the menu will randomly get some of the entries. Compositing (e.g. gnome 3) also solves the problem.
Also seeing this in ThinLinc (a VNC server) in multiple versions:
- SLED 11: 3.6.5.2.15
- Fedora 18: 3.6.6.2
- Fedora 19: 4.0.3.3
So it seems to be a general bug rather than something distribution specific.
Looking at the behaviour, it looks a bit like there is a race going on between the code filling out the menu, and the code blitting it to the X server. Opening the menu will randomly get some of the entries. Compositing (e.g. gnome 3) also solves the problem.