Ubuntu – 16.04 Can’t use bluetooth A2DP headphones, pairs but does not connect. Logs inside

First of, I have tried following both of these: https://vilimpoc.org/blog/2016/04/30/ubuntu-16-04-bluetooth-speakers/ and PulseAudio can not load bluetooth module 15.10/16.04/16.10

When I try to connect my Jaybird X2 (tried on both desktop and laptop, broadcom and intel) it pairs, connects for two seconds then disconnects.

Log form syslog (from my desktop with broadcom BT)

May 31 23:50:54 desktop pulseaudio[6247]: [pulseaudio] socket-server.c: bind(): Address already in use
May 31 23:50:54 desktop pulseaudio[6247]: [pulseaudio] module.c: Failed to load module "module-cli-protocol-unix" (argument: ""): initialization failed.
May 31 23:50:54 desktop pulseaudio[6247]: [pulseaudio] socket-server.c: bind(): Address already in use
May 31 23:50:54 desktop pulseaudio[6247]: [pulseaudio] module.c: Failed to load module "module-cli-protocol-unix" (argument: ""): initialization failed.

And other times:

a2dp-sink profile connect failed for xxxxxxx Protocol not available

EDIT.. IMPORTANT:

I have now found out that trying to connect to other devices work fine (Micropod BT and Samsung AirTrack) most of the time, but as soon as I try Jaybird X2, it disables/unloads module-bluetooth-discover and I have to pactl load-module module-bluetooth-discover for the other two to function again..

Now this happens with laptop:

May 31 17:02:58 vooze-x1 pulseaudio[3534]: [pulseaudio] backend-native.c: connect(): Function not implemented
May 31 17:02:58 vooze-x1 pulseaudio[3534]: [pulseaudio] volume.c: Assertion 'pa_channels_valid(channels)' failed at pulse/volume.c:74, function pa_cvolume_set(). Aborting.
May 31 17:02:58 vooze-x1 bluetoothd[865]: Endpoint unregistered: sender=:1.130 path=/MediaEndpoint/A2DPSource
May 31 17:02:58 vooze-x1 bluetoothd[865]: Endpoint unregistered: sender=:1.130 path=/MediaEndpoint/A2DPSink
May 31 17:03:00 vooze-x1 pulseaudio[3764]: [pulseaudio] main.c: User-configured server at {ddcf951d58914c47b9adca0056c50142}unix:/run/user/1000/pulse/native, which appears to be local. Probing deeper.
May 31 17:03:00 vooze-x1 pulseaudio[3767]: [pulseaudio] pid.c: Stale PID file, overwriting.

I was briefly able to connect it on my desktop before, but A2DP was not working most of the time..

Two different errors but same issue. What is going on?

Is bluetooth just broken in Ubuntu 16.04?
It works in Windows and with my Android Phone.

Any help would be awesome! 🙂 I somehow managed to make it work briefly, first it worked, then A2DP did not work.. so I suspect this have something to do with A2DP. Not sure.