I've also run into this behaviour using the button at the bottom of the screen to toggle between shuffle and in-order. Now those options in the playlist menu are greyed out (see attached screenshot).
If I then reload the playlist (with the same content) using the "replace current playlist" right-click option from the libray, then both the buttons and the menu are working again. Nick
<<attachment: clementine-menu.png>>