Everything works with Nokia BH-604. Jaybird X2 connects and after a few seconds disconnects. Both headsets work with Windows 8.1 in the same computer (dual boot). Using blueman-manager 2.0.4 I get the error in topic. How do I get Jaybird X2 to work with Ubuntu Gnome 16.04?
This solution worked for me: https://zach-adams.com/2014/07/bluetooth-audio-sink-stream-setup-failed/
Delete the device from bluetooth devices and pair it again.
I got a new laptop, plugged in the harddisk from the non-working-bluetooth-laptop and everything worked. So this is most likely a hardware version problem, i.e. Jaybird bluetooth does not support older bluetooth hardware.