I think that Bluetooth and notification volume is tied to media volume, i had this bug too in 3.5. Just ramp up the media volume and see how it goes.
I have the same problem and I test if the problem is it. You theory is correct: Bluetooth and Notification volumen is tied to media volumen. I have a pair of S4 and iIn both the problem exist. Some idea to fix?