I have some new Sony wireless, and have had this same problem since I got them a few months ago. Sometimes they work fine, and sometimes not. Restart, disconnect, forget, etc. would sometimes work and sometimes not. Tried pretty much everything listed here.
Initially it seemed like it was a telephony issue, but that stopped helping. Updated drivers, stated and stopped all sorts of things.
Finally I found soehitng that worked preceisly when i turned it off: Bluetooth Device (RFCOMM Protocol TDI). This is listed under Bluetooth in Device Manager. I was initially just looking to turn of and on the Bluetooth, but on my iMac, in boot camp the
"Apple Broadcom Built-in Bluetooth" cannot be disabled (only uninstalled). Not really wanting to uninstall, I tried disabling the RFCOMM, and viola, the headphones worked perfectly, and have since (although time will tell).
No idea what this does but the bluetooth keyboard and headphones both work fine so....