I have a different but similar issue, and I am not able to connect to my Bluetooth speaker. After searched a while, I find probably I need to upgrade my BIOS. You can check the BIOS version and release date using the following command:
$ sudo dmidecode -s bios-version
$ sudo dmidecode -s bios-release-date
My desktop is Dell, so I checked the Dell website and found the latest BIOS is 07/09/2015, but my current BIOS release date is in 2014. In addition, using the following command
$ dmesg | grep -i blue
I got the following information, and the error message related to firmware is also a potential indication of outdated BIOS
[ 4.189753] Bluetooth: Core ver 2.19
[ 4.189788] Bluetooth: HCI device and connection manager initialized
[ 4.189793] Bluetooth: HCI socket layer initialized
[ 4.189794] Bluetooth: L2CAP socket layer initialized
[ 4.189802] Bluetooth: SCO socket layer initialized
[ 4.194508] bluetooth hci0: Direct firmware load failed with error -2
[ 4.194510] bluetooth hci0: Falling back to user helper
[ 4.257609] Bluetooth: hci0: BCM: patch brcm/BCM43142A0-0a5c-21d7.hcd not found
[ 5.837608] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[ 5.837610] Bluetooth: BNEP filters: protocol multicast
[ 5.837616] Bluetooth: BNEP socket layer initialized
[ 5.841032] Bluetooth: RFCOMM TTY layer initialized
[ 5.841038] Bluetooth: RFCOMM socket layer initialized
[ 5.841041] Bluetooth: RFCOMM ver 1.11
Because I have another Windows OS installed on another disk, so I reboot into Windows and downloaded the latest BIOS upgrade EXE from Dell website, and execute it to upgrade my BIOS. After that, I reboot into Ubuntu, and it works like a charm.
lsusb
return in terminal?