On my S4 with Android 4.3, the above worked (when all else did not). I no longer have Samsung Music on my lock screen. I would, however, like to have "Music" (the music app with the light blue box and music note icon - AT&T maybe) appear on my lock screen, replacing the now absent Samsung Music. What do I need to do (or not do, since the Samsung player seemed to magically appear)??
OK, should have tried before I asked..... I just started the player from my home screen and it is now on the lock screen too. Everything is in sync...... Life is good.
BTW, if you have "Adapt Sound" available on the bottom of the "Sound" settings menu, definitely run through it with your headphones. Do it in a quiet room. What a difference it makes in playback! It eq's the sound to match your earphones and your ears.