I just want to know one thing sure:

is it only the playlist where shuffling doesn't work or doesn't it work in the video, music, image viewers as well?
The default playlist "Queue" is not really a playlist. It's a queue where queued items get removed after playing. The "Queue" currently does not shuffle. You can add real playlist in the playlist viewer. Those do support shuffle.

But if shuffling doesn't work anywhere for you, then I guess there's a real bug that needs more investigation.