If anyone is running kernel 5.4.0-1042-raspi Ubuntu Server 20.04 for Raspberry Pi. The below instructions worked for me.
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
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):
Credit: Edward Torvalds, Julian on StackExchange
Original Thread: https://unix.stackexchange.com/question ... ror-failed