I just want to weigh in and throw my support behind having a truly random shuffle option, or at least a shuffle algorithm that doesn't weigh individual tracks quite so heavily. I'm considering switching services to find one that will actually hit all songs on a playlist, given time.
I got an email that said that this issue has been solved, but when I clicked on "Go to Solution" in the original post on this thread, it took me to a reply on this thread that is not a solution but just another complaint. I think this issue needs to be reopened because to my knowledge the problem has not be solved.
I am having this same issue - 250+ soung playlist and the same 15 or so songs keep coming up. It's just runing these songs for me - I inteded on hearing them once or twice a week, not four times a week!
I have figured out on Android at least if you go into the settings and then application manager and clear cache and data from spotify, it seems to become random again. It is annoying but I am hearing songs I haven't heard in a while soooooo :)
Might as well have my twopence worth as well. I see this thread is at least a year and a half old and the complaint is still exactly the same. I have over 800 songs in my favourites and appear to be stuck with the same twenty or thirty repeated ad nauseum. Obviously Spotify have an agenda, just can't figure it out. Even I can get too much Bob Dylan and the Rolling Stones and, strangely, Supertramp.