What Bluetooth controllers are you using? Is the Linux/Windows machine the same machine?
Not all bluetooth cheaps are equal. My phone will do Bluetooth all the way at the end of my back yard, but my desktop’s Bluetooth doesn’t even reliably reach the next room over.
I doubt it’s the headset, unless it’s defective and you need a replacement, those are pretty well regarded. I have a cheaper model and it’s been a flawless experience for years.