Error when trying to connect to bluetooth speaker: `org.bluez.Error.Failed`

This may be due to the pulseaudio-module-bluetooth package not being installed. Install it if it missing, then restart pulseaudio.

sudo apt install pulseaudio-module-bluetooth 
pulseaudio -k
pulseaudio --start

If the issue is not due to the missing package, the problem in this case is that PulseAudio is not catching up. A common solution to this problem is to restart PulseAudio. Note that it is perfectly fine to run bluetoothctl as root while PulseAudio runs as user. After restarting PulseAudio, retry to connect. It is not necessary to repeat the pairing.

Continue trying second part only if above does not work for you:

If restarting PulseAudio does not work, you need to load module-bluetooth-discover.

sudo pactl load-module module-bluetooth-discover

The same load-module command can be added to /etc/pulse/default.pa. If that still does not work, or you are using PulseAudio's system-wide mode, also load the following PulseAudio modules (again these can be loaded via your default.pa or system.pa):

module-bluetooth-policy
module-bluez5-device
module-bluez5-discover

Try trusting the device first before paring the device.
I got the same error while attempt to pair my AirPods to Ubuntu 16.04.
In bluetoothctl with sudo I got

Attempting to pair with XX:XX:XX:XX:XX:XX  
Failed to pair: org.bluez.Error.AuthenticationCanceled

Attempting to connect to XX:XX:XX:XX:XX:XX  
Failed to connect: org.bluez.Error.Failed

Now this is what I've tried (full progress)

$ sudo bluetoothctl
[bluetooth]# power on
[bluetooth]# agent on
[bluetooth]# default-agent
[bluetooth]# scan on
[NEW] Device XX:XX:XX:XX:XX:XX David's AirPods
[bluetooth]# scan off
[bluetooth]# trust XX:XX:XX:XX:XX:XX
[bluetooth]# pair XX:XX:XX:XX:XX:XX
Attempting to pair with XX:XX:XX:XX:XX:XX
[CHG] Device XX:XX:XX:XX:XX:XX Connected: yes
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX UUIDs: ... 
[CHG] Device XX:XX:XX:XX:XX:XX Paired: yes
Pairing successful
[CHG] Device XX:XX:XX:XX:XX:XX Connected: no
[bluetooth]# connect XX:XX:XX:XX:XX:XX
Attempting to connect to XX:XX:XX:XX:XX:XX
[CHG] Device XX:XX:XX:XX:XX:XX Connected: yes
Connection successful
[bluetooth]# quit

Now the AirPods works beautifully between my iPhone and Ubuntu.

this procedure works for me, thx.

additional comments:

I was trying to add a bluetooth speaker, this was the error message that I had,

[NEW] Device FC:58:FA:B9:BF:A1 Anker A7910
[bluetooth]# connect FC:58:FA:B9:BF:A1
Attempting to connect to FC:58:FA:B9:BF:A1
[CHG] Device FC:58:FA:B9:BF:A1 Connected: yes
Failed to connect: org.bluez.Error.Failed
[CHG] Device FC:58:FA:B9:BF:A1 Connected: no
[CHG] Device FC:58:FA:B9:BF:A1 Connected: yes
[CHG] Device FC:58:FA:B9:BF:A1 Connected: no

I removed the device and then repeat all the steeps that David Jung share.

this is how it looks now:

[Anker A7910]# info FC:58:FA:B9:BF:A1
Device FC:58:FA:B9:BF:A1
    Name: Anker A7910
    Alias: Anker A7910
    Class: 0x260404
    Icon: audio-card
    Paired: yes
    Trusted: yes
    Blocked: no
    Connected: yes
    LegacyPairing: yes
    UUID: Serial Port               (00001101-0000-1000-8000-00805f9b34fb)
    UUID: Audio Sink                (0000110b-0000-1000-8000-00805f9b34fb)
    UUID: A/V Remote Control Target (0000110c-0000-1000-8000-00805f9b34fb)
    UUID: A/V Remote Control        (0000110e-0000-1000-800

Thx again