I also did the update (from 2.34 to 2.36) and what struck me is that when a list of music is played in random mode, it plays a lot of the same artist.
I mean with this that for example I have artist A, B, C and D in one list. First it plays a lot of artist A then a lot of music from artist C etc..
Before it played one song of A then another one of C and then another one of D, with other words really at random, now it looks like this isn't the case anymore. I will try it again this afternoon.