I've also been experiencing problems with my music skipping while streaming for the past few weeks. I thought it was a problem with Spotify at first, but this morning I was listening to Soundcloud and experienced the exact same thing, although less frequently. It seems to happen only when my phone is locked, and extra when I'm walking or moving (this doesnt really make any sense, but pretty sure its true). I know its not my headphones, because i can listen to other apps, such as youtube, snapchat, or facebook, with no problems. I have all the songs on my spotify downloaded to my phone, so it shouldn't be related to streaming via LTE.