Ubuntu 18.04 - Bluetooth não funciona

Estou usando o Ubuntu 18.04 LTS e meu laptop não está escaneando outros dispositivos. Todos os dispositivos que estou tentando conectar são totalmente funcionais e funcionam com outros dispositivos e plataformas.

Eu tentei o seguinte:

$ bluetoothctl

E isso é o que eu recebo:

[NEW] Controller 34:23:87:DC:89:A8 Linux [default]
Agent registered
[bluetooth]# power on
Changing power on succeeded
[bluetooth]# scan on
Discovery started
[CHG] Controller 34:23:87:DC:89:A8 Discovering: yes
[bluetooth]# list
Controller 34:23:87:DC:89:A8 Linux [default]
[bluetooth]# devices
[bluetooth]# exit
Agent unregistered
[DEL] Controller 34:23:87:DC:89:A8 Linux [default]

Tentei as seguintes soluções:

1. https://askubuntu.com/a/1043219/1053060
2. https://askubuntu.com/a/808114/1053060

ATUALIZAÇÃO: Saída de sudo service bluetooth status:

● bluetooth.service - Bluetooth service
   Loaded: loaded (/lib/systemd/system/bluetooth.service; enabled; vendor preset: enabled)
   Active: active (running) since Tue 2020-03-17 22:36:42 PKT; 8min ago
     Docs: man:bluetoothd(8)
 Main PID: 729 (bluetoothd)
   Status: "Running"
    Tasks: 1 (limit: 4545)
   CGroup: /system.slice/bluetooth.service
           └─729 /usr/lib/bluetooth/bluetoothd

Mar 17 22:36:42 Linux systemd[1]: Starting Bluetooth service...
Mar 17 22:36:42 Linux bluetoothd[729]: Bluetooth daemon 5.48
Mar 17 22:36:42 Linux systemd[1]: Started Bluetooth service.
Mar 17 22:36:42 Linux bluetoothd[729]: Starting SDP server
Mar 17 22:36:42 Linux bluetoothd[729]: Bluetooth management interface 1.14 initialized
Mar 17 22:37:10 Linux bluetoothd[729]: Endpoint registered: sender=:1.81 path=/MediaEndpoint/A2DPSource
Mar 17 22:37:10 Linux bluetoothd[729]: Endpoint registered: sender=:1.81 path=/MediaEndpoint/A2DPSink