Ubuntu – Unable to connect to bluetooth devices (org.bluez.Error.ConnectionAttemptFailed)

I am unable to connect* to bluetooth devices. Scanning will find my devices after a couple minutes, but pairing will not succeed. When using the Settings GUI, it shows my device as "Not Set Up". Clicking on it will show a spinning wheel for a minute, after which it will return to "Not Set Up".

Using bluetoothctl, when attempting to pair to a device, I get "org.bluez.Error.ConnectionAttemptFailed"

This happens while attempting to pair several different bluetooth devices (headset, speaker, phone) to my computer.

Currently running Ubuntu 20.04 (upgraded from 18.04), kernel 5.4.0-37-generic

I had the same issues while running 18.04 on this computer, also with a 20.04 live-USB to rule out anything that I might have changed from default.

My bluetooth devices is:
03:00.0 Network controller: Intel Corporation Dual Band Wireless-AC 3168NGW [Stone Peak] (rev 10)

user@computer:~$ dmesg | grep -i blue
[   21.690128] Bluetooth: Core ver 2.22
[   21.690138] Bluetooth: HCI device and connection manager initialized
[   21.690141] Bluetooth: HCI socket layer initialized
[   21.690142] Bluetooth: L2CAP socket layer initialized
[   21.690147] Bluetooth: SCO socket layer initialized
[   21.755854] Bluetooth: hci0: read Intel version: 370810225019140f00
[   21.758971] Bluetooth: hci0: Intel Bluetooth firmware file: intel/ibt-hw-37.8.10-fw-22.50.19.14.f.bseq
[   22.083912] Bluetooth: hci0: Intel firmware patch completed and activated
[   23.196241] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[   23.196242] Bluetooth: BNEP filters: protocol multicast
[   23.196245] Bluetooth: BNEP socket layer initialized
[   23.318920] Bluetooth: RFCOMM TTY layer initialized
[   23.318924] Bluetooth: RFCOMM socket layer initialized
[   23.318927] Bluetooth: RFCOMM ver 1.11

user@computer:~$ systemctl status bluetooth.service
● bluetooth.service - Bluetooth service
     Loaded: loaded (/lib/systemd/system/bluetooth.service; enabled; vendor preset: enabled)
     Active: active (running) since Tue 2020-06-16 10:34:31 PDT; 39min ago
       Docs: man:bluetoothd(8)
   Main PID: 1115 (bluetoothd)
     Status: "Running"
      Tasks: 1 (limit: 19013)
     Memory: 2.3M
     CGroup: /system.slice/bluetooth.service
             └─1115 /usr/lib/bluetooth/bluetoothd

Jun 16 10:34:30 computer systemd[1]: Starting Bluetooth service...
Jun 16 10:34:30 computer bluetoothd[1115]: Bluetooth daemon 5.53
Jun 16 10:34:31 computer bluetoothd[1115]: Starting SDP server
Jun 16 10:34:31 computer systemd[1]: Started Bluetooth service.
Jun 16 10:34:31 computer bluetoothd[1115]: Bluetooth management interface 1.14 initialized
Jun 16 10:35:35 computer bluetoothd[1115]: Endpoint registered: sender=:1.83 path=/MediaEndpoint/A2DPSink/sbc
Jun 16 10:35:35 computer bluetoothd[1115]: Endpoint registered: sender=:1.83 path=/MediaEndpoint/A2DPSource/sbc

user@computer:~$ bluetoothctl
Agent registered
[bluetooth]# power on
Changing power on succeeded
[bluetooth]# scan on
Discovery started
[CHG] Controller 10:F0:05:XX:XX:XX Discovering: yes
[bluetooth]# pairable on
Changing pairable on succeeded
[CHG] Device 5C:FB:7C:XX:XX:XX RSSI: -84
[CHG] Device 5C:FB:7C:XX:XX:XX TxPower: 4
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110d-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110b-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110e-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110f-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000111e-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 00001108-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 00001131-0000-1000-8000-00805f9b34fb
[bluetooth]# trust 5C:FB:7C:XX:XX:XX
Changing 5C:FB:7C:XX:XX:XX trust succeeded
[bluetooth]# pair 5C:FB:7C:XX:XX:XX
Attempting to pair with 5C:FB:7C:XX:XX:XX
Failed to pair: org.bluez.Error.ConnectionAttemptFailed
[bluetooth]# exit

I would appreciate any help!

*A couple of times, using bluetoothctl I was able to get it to briefly say it paired and connected, but it would immediately say disconnected afterwards. I am currently unable to replicate this.

Update

Still made no progress on figuring out the issue, but I did catch it saying that it connected to the device and immediately disconnecting:

user@computer:~$ bluetoothctl
Agent registered
[bluetooth]# power on
Changing power on succeeded
[bluetooth]# scan on
Discovery started
[CHG] Device 5C:FB:7C:XX:XX:XX RSSI: -80
[CHG] Device 5C:FB:7C:XX:XX:XX RSSI: -84
[CHG] Device 5C:FB:7C:XX:XX:XX RSSI: -77
[bluetooth]# trust 5C:FB:7C:XX:XX:XX
[CHG] Device 5C:FB:7C:XX:XX:XX Trusted: yes
Changing 5C:FB:7C:XX:XX:XX trust succeeded
[bluetooth]# pair 5C:FB:7C:XX:XX:XX
Attempting to pair with 5C:FB:7C:XX:XX:XX
[CHG] Device 5C:FB:7C:XX:XX:XX Connected: yes
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 00001108-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110b-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110c-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000110e-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 0000111e-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 00001124-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX UUIDs: 00001200-0000-1000-8000-00805f9b34fb
[CHG] Device 5C:FB:7C:XX:XX:XX ServicesResolved: yes
[CHG] Device 5C:FB:7C:XX:XX:XX Paired: yes
Pairing successful
[CHG] Device 5C:FB:7C:XX:XX:XX ServicesResolved: no
[CHG] Device 5C:FB:7C:XX:XX:XX Connected: no
[bluetooth]# 

Any thoughts for further troubleshooting would be greatly appreciated!