Need help? Check out Spotify Answers for solutions to a wide range of topics.
my carrier is Verizon, USA, my phone is a samsung galaxy s3, and it happens on wifi or on the verizon network.
I recommend you contact Spotify Support using the form here. It may be they just need to clear your cache their sideYou will get an automated reply at first, however if you need to chase them just reply to the email as it does get monitored.