I've been experiencing the same problem, or at least what I think is the same problem. I will be listening to a song over LTE or WiFi with full bars, or close to it and about half way through the song it will pause for 5 seconds begin playing where it left off and pause again for a split second, then play again. This happen almost within every song. Although it sounds like a buffering problem my theory is that the problem lies within in the app, specifically the adroid version on my phone. I does not happen on my wife's iPhone, nor my Mac Mini or Dell work computer.
I have tried reinstalling the app twice. Adjusting the song quality - tried them all. Disabling Nuplayer (which wasn't enabled on my phone in the first place). Installing a cache cleaner and making sure cache has been cleared before playback. Deleting old apps that I no longer use. You get the point.
1. Exact Device - Samsung Galaxy Note Edge
2. Exact operating system - 5.0.1
3. Spotify app version installed - 184.108.40.2064
4. What are you doing when the app skips/ stops/ crashes? Is it when it opens? When scrolling through tracks? When searching? - In most cases I am doing nothing within the app. The screen is either locked or open and a playlist is playing. It happens both directly in the app and when on my home screen, just as a note I do use the widget if that makes a difference.
5. About how many playlists do you have? Around 30 playlists - if this matters I can certainly delete a few
I'm getting to the point now where I would rather just factory reset my phone but really don't want to have to. I am a huge fan of Spotify and would hate to have to cancel the service as I use the family plan with 5 accounts.