Pickone Since there is now a report from a 7a owner with Beats Pro without this issue (longshots), and since your headphones work fine with some other phone, it seems plausible that there is some settings issue on your phone, or perhaps some corrupted data.
I realize this would probably be annoying, but in Settings, System, Reset options there is a "Reset Bluetooth & Wi-Fi" option. I don't know exactly what it does, but I suspect it would be less disruptive than wiping your whole phone...