I'm having the same problem! It's driving me crazy. I've tried clearing cache, uninstalling the app, trying different songs / playlists.
I've tried two different ROM's thinking that maybe it was the new ROM I installed. Also having similar issues on my tablet. Both devices will download some tracks then fail with others but it's never the same songs or playlists.
My phone is a Verizon HTC One M8 and i'm having trouble on Sense ROM's, GPE and LiquidSmooth as well as issues on my Verizon LG G Pad 8.3
In my pocket:
Device: Verizon HTC One
Verizon LG GPad 8.3
ROM: Stock for now.
On my desk:
Asus G73JH - A1
i7 720qm 1.6ghz
Radeon 5870m w/1gb DDR5
2x 500gb HD's (1x Seagate Momentus XT)
17.3 inch Full HD LED Display
Follow me on Twitter: https://twitter.com/edge191