Samsung GS3 - Spotify Mutes After Each Song While Using Headphones

[Pinchered]

As the title says, Spotify mutes after every song when I'm using headphones. It's driving me crazy! I have to pause the new song (that is playing without sound); unplug my headphones; replug my headphones; and then I can hit play again to get sound. This is highly distracting as I use Spotify at work. It really puts a kink in my work flow to lose my place every few minutes when I have to reset the sound on my device.

This just started after I upgraded to Jelly Bean the other week. I've tried deleting & reinstalling the app. I've cleared all cache data. I've tried using other programs (the issue doesn't persist with them). I am getting very frustrated at this point. Is there a way to fix it?

[unfoundbug]

I have had the same issue on my device for a while, I thought it was due to a faulty SD card as my other music apps were having playback issues, but now I have replaced it its still there.

This only seems to happen while I am offline which is extremely annoying as this is when I usually use spotify, while travelling.