I have decided that the Spotify app is the problem and not my phone or my headset. I have LG Tone Ultra (HBS-800), and my phone is the LG G3. Previously I had the HTC Droid DNA, and I experienced the same problems with both. My bluetooth headset never loses connection with the phone, but somehow the Spotify app stops recognizing the play/pause and FW/RW buttons. The volume buttons always work. At first I thought it was the headset and had it replaced. But, of course, the new headset has the same problem. Because the phone never loses connection, I don't believe it is the phone either. So that leaves the Spotify app itself.
Basically, I am not able to control the app when the phone is locked...which defeats the purpose of having these buttons in the first place and the whole hands-free concept goes out the window! I have tested this many times in many different ways, and the problem is definitely the app. I can see clearly that the buttons do work. When my phone goes to sleep, if I press a button, the phone wakes up and goes back to the Spotify screen, but the buttons still do not work. Same issue when the phone is actually fully locked. The only way I've found to "wake up" the button connection again is to press the call button, but who wants to do that every 15 minutes? Please fix this! It is extremely frustrating--especially while I am driving.