Cannot pair my beats 3 bluetooth headset with Ubuntu 16.04 LTS

I've just had the very same problem : my brand new Beats Solo 3 headset wouldn't pair with Bluetooth on my Aver Swift 3, with Ubuntu 20.04. I spent a morning reading help forums, installed Blueman, rebooted everything 5 times, and finally found a tip that solved everything in 2 minutes. In case it can help anyone :

1. Find the Bluetooth ID of your device (Blueman was helpful there, but any other Bluetooth manager works). If you don't have any I suggest :

user@computer:~$ sudo apt-get install blueman

then to lauch

user@computer:~$ blueman-manager

This opens a minimalist interface where you can identify at once the available Bluetooth devices. If your issue is not about detecting your device, you should see it with its ID (something like 56:D5:98:02:FF:9P). You can always try clicking on your device and selecting "pair", but for me it failed.

2. Open bluetoothctl

user@computer:~$ bluetoothctl

It should tell you something like

agent registered
[bluetooth]#

(if a device is already paired, its name is written instead of "bluetooth").

3. Run scan :

[bluetooth]# agent on
[bluetooth]# default-agent
[bluetooth]# scan on

This may take some time, and display some lines like this (new lines keep coming every now and then) :

Discovery started
[CHG] Device XX:XX:XX:XX:XX:XX
[NEW] Device XX:XX:XX:XX:XX:XX
[NEW] Device XX:XX:XX:XX:XX:XX
[bluetooth]#

My device wouldn't appear so I jumped to the next step, failed to pair, ran the scan again and this time it showed up.

4. When your device XX:XX:XX:XX:XX:XX appears, you can interrupt the scan and attempt pairing. Before, set the device to trusted :

[bluetooth]# trust XX:XX:XX:XX:XX:XX
changing XX:XX:XX:XX:XX:XX trust succeeded
[bluetooth]# pair XX:XX:XX:XX:XX:XX
attempting to pair with XX:XX:XX:XX:XX:XX
[bluetooth]#

This may again take a while but should display eventually

[CHG] Device XX:XX:XX:XX:XX:XX Connected: yes
Connection successful
[DeviceName]#

If it doesn't, then try again the steps authenticate - scan - trust - pair, perhaps switching your Bluetooth off and on too.

5. Select the right sound output in Parameters > Sound, and enjoy your fancy headset at last.

Hope this helps (I'm myself a beginner juste trying to explain what I stumbled by chance, so probably my tutorial is not top quality).

Try executing the following commands:

sudo apt install pulseaudio-module-bluetooth
sudo killall pulseaudio
sudo service bluetooth restart

Then, try to connect your device again using Blueman (Bluetooth Manager).