I had the same problem but the exclusion of songs was limed to explicit songs. So I went on my phone and went under settings -> Explicit Content and then I allowed Explicit Content by turning it on. Then I went back to my computer and I logged out of Spotify and restarted it and logged back in and then the problem was gone. I hope I helped someone in the making of this post.
Unfortunately, the problem occurred once again on my pc, and this time my earlier solution (updating/installing java and adobe flash & shockwave) doesn't take, Reinstalling neither. Don't know what to do.
Very frustrating, also because many others seem to have the same problem, and I counted tenths of possible solutions on the forums here, that may of may not work.
Bizarre....I downgraded again to my old Realtek high def audio drivers (because of volume issues with the new, updated, driver), so I had the exact situation where my spotify windows app wouldn't work whatsoever, and now it still runs normally...
You need to delete the locally saved app data. Don't worry, doing this won't erase your actual saved app usage info like playlists and songs and artists, but it will erase your recent history list. The simple way to do this is to quit Spotify, then open 'Terminal' app on OSX, and paste this into your terminal, and hit enter:
cd ~/Library/Application\ Support/ && rm -rf Spotify/
If this doesn't work, type it in manually, because sometimes the copy-paste clipboard doesn't properly paste the minus/dash symbol, aka: