It's a Linux + bluetooth problem, not a computer vendor problem. Bluetooth microphones are basically impossible to get working on Linux. That's what I was told by vendor support as well, just get a wired mic as bluetooth headphones+mic are unreliable.

I was attempting to use Sony XM3s.

Glad to hear you have some headphones that work, what model?