Bluetooth headset not working in 20.04 [duplicate]

I have a Lenovo laptop, on which I run Ubuntu. I have a pair of bluetooth headphones which I have used with the laptop for some time, without problems. Now I have updated to 20.04, and the headphones do not work: I have checked that i) bluetooth is working, ii) the pulseaudio and pulseaudio-module-blutooth module are installed, iii) bluetooth sees the headphones, and iv) the computer thinks it is sending audio to bluetooth, but the sound actually comes out through the laptop speakers.

systemctl status bluetooth says this:
● bluetooth.service - Bluetooth service
     Loaded: loaded (/lib/systemd/system/bluetooth.service; enabled; vendor preset: enabled)
     Active: active (running) since Sat 2020-04-25 13:18:52 BST; 22min ago
       Docs: man:bluetoothd(8)
   Main PID: 11368 (bluetoothd)
     Status: "Running"
      Tasks: 1 (limit: 9341)
     Memory: 1.8M
     CGroup: /system.slice/bluetooth.service
             └─11368 /usr/lib/bluetooth/bluetoothd

Apr 25 13:18:52 malebranche bluetoothd[11368]: Bluetooth daemon 5.53
Apr 25 13:18:52 malebranche systemd[1]: Started Bluetooth service.
Apr 25 13:18:52 malebranche bluetoothd[11368]: Starting SDP server
Apr 25 13:18:52 malebranche bluetoothd[11368]: Bluetooth management interface 1.14 initialized
Apr 25 13:18:52 malebranche bluetoothd[11368]: Endpoint registered: sender=:1.173 path=/MediaEndpoint/A2DPSink/sbc
Apr 25 13:18:52 malebranche bluetoothd[11368]: Endpoint registered: sender=:1.173 path=/MediaEndpoint/A2DPSource/sbc
Apr 25 13:19:45 malebranche bluetoothd[11368]: /org/bluez/hci0/dev_E8_07_BF_04_1B_D0/sep1/fd0: fd(38) ready
Apr 25 13:21:35 malebranche bluetoothd[11368]: /org/bluez/hci0/dev_E8_07_BF_04_1B_D0/sep1/fd1: fd(53) ready
Apr 25 13:30:53 malebranche bluetoothd[11368]: Unable to get io data for Headset Voice gateway: getpeername: Transport endpoint is not connected (107)
Apr 25 13:31:09 malebranche bluetoothd[11368]: /org/bluez/hci0/dev_E8_07_BF_04_1B_D0/sep1/fd2: fd(53) ready

However, the sound settings panel says that the sound output is through the headset, but when I press the "test" button, sound comes out through the laptop speakers. This happens both when the configuration is A2DP or HSP/HFP So, the GUI says that all is well, whereas systemctl status says that something is going wrong.

I had the exact same situation upgrading from 19.10 to 20.04 with a HP laptop and Skullcandy Bluetooth headphones: Using the sound panel and changing the output to the headphone does not work. However using the pulse-audio volume control and switching the output to the headphone redirect the sound to them.

Pulse audio should be installed but in case it is not:

sudo apt install pulseaudio pulseaudio-module-bluetooth

To the Ubuntu team: that is a bug to be fixed.

Cheer!