I just solved a problem that has haunted me for a month so I figured I'd share here for the benefit of eveyone.
Samsung Galaxy S3, Android 4.4.2, Spotify 3.4.
When connected through an A2DP Bluetooth 3 device (Sena SMH-10), as soon as a notification would pop up, the music would start stuttering (even offline). Did not do that in my car (Bluetooth 4.1). I tried every fix, rollback, 3rd party app that was supposed to solve the issue. Nothing did it and getting the phone back to factory wasn't an option at all. At first, I thought it had something to do with the July update because it was a nightmare filled with bugs, most of them quickly fixed afterwards in the following update. But the bluetooth stuttering problem stayed.
I ended up looking at my running apps and found running applications that were leeching so many resources that it overloaded the CPU. In my case, deleting the Wimbledon Championship application fixed the issue instantly. The app was ranked 3rd in memory consumption, even more than Spotify itself (which is, lets face it, a heavyweight to carry in this regard)!
I was SO GLAD to find this I cannot keep it to myself.