Marley Exodus ANC Bluetooth headphone won't pair in 21.04

I just bought a new Bluetooth headphone, the Marley Exodus ANC, but it won't pair with my PC (Intel NUC) in Ubuntu 21.04. When trying to connect from GNOME settings, it attempts to pair but it just gives up without an error message.

I also tried to manually connect using bluetoothctl:

$ bluetoothctl
[bluetooth]# show
Controller 04:EA:56:86:78:50 (public)
        Name: saibot
        Alias: saibot
        Class: 0x003c0104
        Powered: yes
        Discoverable: no
        DiscoverableTimeout: 0x00000000
        Pairable: yes
        UUID: Message Notification Se.. (00001133-0000-1000-8000-00805f9b34fb)
        UUID: A/V Remote Control        (0000110e-0000-1000-8000-00805f9b34fb)
        UUID: OBEX Object Push          (00001105-0000-1000-8000-00805f9b34fb)
        UUID: Message Access Server     (00001132-0000-1000-8000-00805f9b34fb)
        UUID: PnP Information           (00001200-0000-1000-8000-00805f9b34fb)
        UUID: IrMC Sync                 (00001104-0000-1000-8000-00805f9b34fb)
        UUID: Vendor specific           (00005005-0000-1000-8000-0002ee000001)
        UUID: Headset                   (00001108-0000-1000-8000-00805f9b34fb)
        UUID: Headset AG                (00001112-0000-1000-8000-00805f9b34fb)
        UUID: A/V Remote Control Target (0000110c-0000-1000-8000-00805f9b34fb)
        UUID: Generic Attribute Profile (00001801-0000-1000-8000-00805f9b34fb)
        UUID: Phonebook Access Server   (0000112f-0000-1000-8000-00805f9b34fb)
        UUID: Audio Sink                (0000110b-0000-1000-8000-00805f9b34fb)
        UUID: Device Information        (0000180a-0000-1000-8000-00805f9b34fb)
        UUID: Generic Access Profile    (00001800-0000-1000-8000-00805f9b34fb)
        UUID: Audio Source              (0000110a-0000-1000-8000-00805f9b34fb)
        UUID: OBEX File Transfer        (00001106-0000-1000-8000-00805f9b34fb)
        Modalias: usb:v1D6Bp0246d0538
        Discovering: no
        Roles: central
        Roles: peripheral
        Roles: central-peripheral
Advertising Features:
        ActiveInstances: 0x00 (0)
        SupportedInstances: 0x06 (6)
        SupportedIncludes: tx-power
        SupportedIncludes: appearance
        SupportedIncludes: local-name
        SupportedSecondaryChannels: 1M
        SupportedSecondaryChannels: 2M
        SupportedSecondaryChannels: Coded

[bluetooth]# scan on
Discovery started   

[NEW] Device 00:1E:7C:89:26:C8 Exodus ANC

[bluetooth]# connect 00:1E:7C:89:26:C8
Attempting to connect to 00:1E:7C:89:26:C8
Failed to connect: org.bluez.Error.Failed

[bluetooth]# pair 00:1E:7C:89:26:C8
Attempting to pair with 00:1E:7C:89:26:C8
Failed to pair: org.bluez.Error.AuthenticationTimeout

I also looked for system errors:

$ sudo journalctl -xb
bluetoothd[1208]: 00:1E:7C:89:26:C8: error updating services: Function not implemented (38)

$ dmesh
Bluetooth: hci0: advertising data len corrected

I have another Bluetooth headphone and I can pair that one just fine. And I can pair the Exodus ANC with my Android phone just fine. But I noticed that when pairing the Exodus ANC with Android, Android displays a PIN code from the Exodus ANC, and then I can confirm the pair. It's possible that this PIN code causes pairing to fail in Ubuntu. What can I do to pair this headphone in Ubuntu?

$ dpkg -l | grep blue
ii  bluez                                      5.56-0ubuntu4.2                                                      amd64        Bluetooth tools and daemons
ii  bluez-cups                                 5.56-0ubuntu4.2                                                      amd64        Bluetooth printer driver for CUPS
ii  bluez-obexd                                5.56-0ubuntu4.2                                                      amd64        bluez obex daemon
ii  gir1.2-gnomebluetooth-1.0:amd64            3.34.5-1                                                             amd64        Introspection data for GnomeBluetooth
ii  gnome-bluetooth                            3.34.5-1                                                             amd64        GNOME Bluetooth tools
ii  libbluetooth3:amd64                        5.56-0ubuntu4.2                                                      amd64        Library to use the BlueZ Linux Bluetooth stack
ii  libgnome-bluetooth13:amd64                 3.34.5-1                                                             amd64        GNOME Bluetooth tools - support library
rc  libkf5bluezqt-data                         5.80.0-0ubuntu1                                                      all          data files for bluez-qt
ii  pulseaudio-module-bluetooth                1:14.2-1ubuntu1.1                                                    amd64        Bluetooth module for PulseAudio sound server
ii  python-bluez                               0.22+really0.22-1build2                                              amd64        Python 2 wrappers around BlueZ for rapid bluetooth development

UPDATE:

Adding additional debugging information as per instructions by fabatera.

$ sudo systemctl stop bluetooth
$ sudo bluetoothd -d -C -E -n                                                                                        
bluetoothd[122796]: Bluetooth daemon 5.56
bluetoothd[122796]: src/agent.c:agent_ref() 0x5592e4338bd0: ref=2
bluetoothd[122796]: src/device.c:bonding_request_new() Requesting bonding for 00:1E:7C:89:26:C8
bluetoothd[122796]: src/agent.c:agent_ref() 0x5592e4338bd0: ref=3
bluetoothd[122796]: src/agent.c:agent_unref() 0x5592e4338bd0: ref=2
bluetoothd[122796]: src/adapter.c:suspend_discovery() 
bluetoothd[122796]: src/adapter.c:adapter_bonding_attempt() hci0 bdaddr 00:1E:7C:89:26:C8 type 0 io_cap 0x04
bluetoothd[122796]: src/adapter.c:connect_failed_callback() hci0 00:1E:7C:89:26:C8 status 8
bluetoothd[122796]: plugins/policy.c:conn_fail_cb() status 8
bluetoothd[122796]: src/adapter.c:bonding_attempt_complete() hci0 bdaddr 00:1E:7C:89:26:C8 type 0 status 0x8
bluetoothd[122796]: src/device.c:device_bonding_complete() bonding 0x5592e433eb20 status 0x08
bluetoothd[122796]: src/device.c:device_bonding_failed() status 8
bluetoothd[122796]: src/agent.c:agent_unref() 0x5592e4338bd0: ref=1
bluetoothd[122796]: src/adapter.c:resume_discovery() 
bluetoothd[122796]: src/adapter.c:pair_device_complete() Timeout (0x08)
bluetoothd[122796]: src/adapter.c:bonding_attempt_complete() hci0 bdaddr 00:1E:7C:89:26:C8 type 0 status 0x8
bluetoothd[122796]: src/device.c:device_bonding_complete() bonding (nil) status 0x08
bluetoothd[122796]: src/device.c:device_bonding_failed() status 8
bluetoothd[122796]: src/adapter.c:resume_discovery() 
bluetoothd[122796]: src/device.c:connect_profiles() /org/bluez/hci0/dev_00_1E_7C_89_26_C8 (all), client :1.829
bluetoothd[122796]: src/device.c:connect_profiles() Resolving services for /org/bluez/hci0/dev_00_1E_7C_89_26_C8
bluetoothd[122796]: src/adapter.c:connect_failed_callback() hci0 00:1E:7C:89:26:C8 status 8
bluetoothd[122796]: plugins/policy.c:conn_fail_cb() status 8
bluetoothd[122796]: src/adapter.c:bonding_attempt_complete() hci0 bdaddr 00:1E:7C:89:26:C8 type 0 status 0x8
bluetoothd[122796]: src/device.c:device_bonding_complete() bonding (nil) status 0x08
bluetoothd[122796]: src/device.c:device_bonding_failed() status 8
bluetoothd[122796]: src/adapter.c:resume_discovery() 
bluetoothd[122796]: src/device.c:search_cb() 00:1E:7C:89:26:C8: error updating services: Function not implemented (38)
bluetoothd[122796]: src/device.c:device_svc_resolved() /org/bluez/hci0/dev_00_1E_7C_89_26_C8 err -38
$ sudo btmon
Bluetooth monitor ver 5.56
= Note: Linux version 5.11.0-25-generic (x86_64)     
= Note: Bluetooth subsystem version 2.22             
= New Index: 04:EA:56:86:78:50 (Primary,USB,hci0)    
= bluetoothd: Bluetooth daemon 5.56                  
@ MGMT Open: bluetoothd (privileged) version 1.19

# pair attempt:

@ MGMT Command: Pair Device (0x0019) plen 8                                                                                                                                                                                                                      {0x0001} [hci0] 154.081112 
        BR/EDR Address: 00:1E:7C:89:26:C8 (Taiwick Limited)                                                                                                                                                                                                                                 
        Capability: KeyboardDisplay (0x04)                             
< HCI Command: Create Connection (0x01|0x0005) plen 13                                                                                                                                                                                                               #141 [hci0] 154.081177 
        Address: 00:1E:7C:89:26:C8 (Taiwick Limited)
        Packet type: 0xcc18                                            
          DM1 may be used                                              
          DH1 may be used                                              
          DM3 may be used                                              
          DH3 may be used                                              
          DM5 may be used                                              
          DH5 may be used                                              
        Page scan repetition mode: R2 (0x02)                           
        Page scan mode: Mandatory (0x00)                                                                                                                                                                                                                                                    
        Clock offset: 0x0000                                           
        Role switch: Allow slave (0x01)                                
> HCI Event: Command Status (0x0f) plen 4                                                                                                                                                                                                                            #142 [hci0] 154.197141
      Create Connection (0x01|0x0005) ncmd 1                           
        Status: Success (0x00)                                                                                                                                                                                                                                                              
> HCI Event: Connect Complete (0x03) plen 11                                                                                                                                                                                                                         #143 [hci0] 186.684630 
        Status: LMP Response Timeout / LL Response Timeout (0x22)      
        Handle: 65535                                                                                                                                                                                                                                                                       
        Address: 00:1E:7C:89:26:C8 (Taiwick Limited)                   
        Link type: ACL (0x01)                                          
        Encryption: Disabled (0x00)                                    
@ MGMT Event: Connect Failed (0x000d) plen 8                                                                                                                                                                                                                     {0x0001} [hci0] 186.684678 
        BR/EDR Address: 00:1E:7C:89:26:C8 (Taiwick Limited)
        Status: Timeout (0x08)                                         
@ MGMT Event: Command Complete (0x0001) plen 10                                                                                                                                                                                                                  {0x0001} [hci0] 186.684696 
      Pair Device (0x0019) plen 7                                      
        Status: Timeout (0x08)                                         
        BR/EDR Address: 00:1E:7C:89:26:C8 (Taiwick Limited)

# connect attempt:

< HCI Command: Create Connection (0x01|0x0005) plen 13                                                                                                                                                                                                               #144 [hci0] 818.218687
        Address: 00:1E:7C:89:26:C8 (Taiwick Limited)
        Packet type: 0xcc18
          DM1 may be used
          DH1 may be used
          DM3 may be used
          DH3 may be used
          DM5 may be used
          DH5 may be used
        Page scan repetition mode: R2 (0x02)
        Page scan mode: Mandatory (0x00)
        Clock offset: 0x0000
        Role switch: Allow slave (0x01)
> HCI Event: Command Status (0x0f) plen 4                                                                                                                                                                                                                            #145 [hci0] 818.333626
      Create Connection (0x01|0x0005) ncmd 1
        Status: Success (0x00)
> HCI Event: Connect Complete (0x03) plen 11                                                                                                                                                                                                                         #146 [hci0] 850.041050
        Status: LMP Response Timeout / LL Response Timeout (0x22)
        Handle: 65535
        Address: 00:1E:7C:89:26:C8 (Taiwick Limited)
        Link type: ACL (0x01)
        Encryption: Disabled (0x00)
@ MGMT Event: Connect Failed (0x000d) plen 8                                                                                                                                                                                                                     {0x0001} [hci0] 850.041111
        BR/EDR Address: 00:1E:7C:89:26:C8 (Taiwick Limited)
        Status: Timeout (0x08)
= bluetoothd: src/device.c:search_cb() 00:1E:7C:89:26:C8: error updating services: Function not implemented (38)                                                                                                                                                                 850.045357
$ bluetoothctl
[bluetooth]# power on
Changing power on succeeded

[bluetooth]# agent on
Agent is already registered

[bluetooth]# default-agent
Default agent request successful

[bluetooth]# info 00:1E:7C:89:26:C8
Device 00:1E:7C:89:26:C8 (public)
        Name: Exodus ANC
        Alias: Exodus ANC
        Class: 0x00240404
        Icon: audio-card
        Paired: no
        Trusted: yes
        Blocked: no
        Connected: no
        LegacyPairing: no

[bluetooth]# pair 00:1E:7C:89:26:C8
Attempting to pair with 00:1E:7C:89:26:C8
Failed to pair: org.bluez.Error.AuthenticationTimeout

[bluetooth]# connect 00:1E:7C:89:26:C8
Attempting to connect to 00:1E:7C:89:26:C8
Failed to connect: org.bluez.Error.Failed

UPDATE 2:

I just tested these headphones on a Dell Latitude 5280 laptop running Ubuntu 20.04, and it was able to pair just fine! The Dell laptop is using an Intel Wireless Bluetooth (device information doesn't give more information). My Intel NUC has a Bluetooth 9460/9560 Jefferson Peak, also by Intel, with which pairing fails. I also have a Lenovo Thinkpad T14, but pairing fails there also. So I bought a USB Bluetooth dongle, the ASUS Bluetooth Adapter USB-BT500, but pairing still fails. What kind of Bluetooth adapter do I need?

UPDATE 3:

Apparently more people are having issues with these Bluetooth adapters:

  • https://linux-hardware.org/?id=usb:8087-0aaa
  • https://linux-hardware.org/?id=usb:0b05-190e

UPDATE 4:

I bought a bunch of USB Bluetooth adapters, to see if they work. Here are the results thus far:

  1. ASUS USB-BT500 Bluetooth 5.0: cannot pair
  2. Edimax BT-8500 Bluetooth 5.0: cannot pair
  3. TP-LINK UB400 Bluetooth 4.0: can pair, can connect, constant jitter in sound when connected to standard USB 3.1 port (blue port), but sound is fine when connected to USB 3.1 always on port (yellow port).

Solution 1:

Try including more info here:

Start daemon in debug, compat, experimental

systemctl stop bluetooth
bluetoohd -d -C -E -n

In another terminal:

btmon

In another terminal:

bluetoothctl 
power on
pairable on
agent KeyboardOnly
default-agent 
info <head phone mac address>
pair <head phone mac address>