I have a 3000 song playlist which I initially had sorted by date added. However, I quickly realized that out of all those songs, it kept playing the same ones. I decided to do some testing, and I realized that shuffle play was only playing songs at the top of the playlist.
When I organized it by artist, it only played songs from artists starting with A. When I organized it by title, it only played songs starting with numbers or A.
However, this issue only seems to occur when the shuffle play is begun from another device. For example, when I decide to begin playing the playlist on my pc from my phone and vice versa.