Started having the same Problem about 2 weeks ago using Atomic Floyd SAF0106/01/00 AirJax Headphones.
Happens with pretty much any Music App be it XBox Music, MixRadio, MusicPlayer or OneMusic.
Had the Phone Factoryreset about 3-4 Times by now with or without restoring from a Backup.
Will see how the RePlugging Solution will work out as it's definitely faster than restarting the Phone everytime this happens.
RePlugging the Headphones indeed solved the Problem after it happened again today... Lets see when this gets fixed.