Comment 9 for bug 183521

I've found out the cause of this problem. It's the "Disable all menu access keys" option accessible from "Edit" > "Keyboard Shortcut". If this option checked , the labels will be gone after the gnome-terminal restarted.
To reproduce this bug maybe you should test it by doing so.