Wanting to give my Lenovo B590 new life, I recently installed Ubuntu 16.04 on it. However, Bluetooth does not work at all anymore; indeed, running lsusb yields
Bus 002 Device 003: ID 058f:6366 Alcor Micro Corp. Multi Flash Reader
Bus 002 Device 002: ID 8087:0024 Intel Corp. Integrated Rate Matching Hub
Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 001 Device 004: ID 04f2:b2fa Chicony Electronics Co., Ltd
Bus 001 Device 003: ID 04ca:2007 Lite-On Technology Corp.
Bus 001 Device 002: ID 8087:0024 Intel Corp. Integrated Rate Matching Hub
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 004 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 003 Device 004: ID 03f0:304a Hewlett-Packard
Bus 003 Device 003: ID 03f0:134a Hewlett-Packard Optical Mouse
Bus 003 Device 002: ID 05e3:0608 Genesys Logic, Inc. Hub
Bus 003 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
As you see, the built-in Broadcom Bluetooth 4.0 is not detected at all, hence I could not follow this other guide. None of the other guides I have found helped much, either; many were technical and aimed at older versions of Ubuntu or were not useful for other reasons. How can I get Bluetooth working? Complete step-by-step guides are very welcome and might be awarded.
Update: As requested in the comments, I provide the output of dmesg | grep -i blue:
[ 11.251690] thinkpad_acpi: rfkill switch tpacpi_bluetooth_sw: radio is unblocked
[ 13.116194] Bluetooth: Core ver 2.21
[ 13.116209] Bluetooth: HCI device and connection manager initialized
[ 13.116212] Bluetooth: HCI socket layer initialized
[ 13.116213] Bluetooth: L2CAP socket layer initialized
[ 13.116217] Bluetooth: SCO socket layer initialized
[ 15.247647] Bluetooth: hci0 command 0x1001 tx timeout
[ 23.242930] Bluetooth: hci0: BCM: Reading local version info failed (-110)
[ 25.250793] Bluetooth: hci0 command 0x1001 tx timeout
[ 33.246178] Bluetooth: hci0: BCM: Reading local version info failed (-110)
[ 34.984665] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[ 34.984668] Bluetooth: BNEP filters: protocol multicast
[ 34.984672] Bluetooth: BNEP socket layer initialized
