I had the same problem with a Lenovo Ideapad 710.
A lsusb return
Bus 002 Device 002: ID 8087:8000 Intel Corp.
Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 001 Device 002: ID 8087:8008 Intel Corp.
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 007: ID 0cf3:3004 Atheros Communications, Inc.
Bus 003 Device 006: ID 03f0:1024 Hewlett-Packard Smart Card Keyboard
Bus 003 Device 005: ID 5986:0295 Acer, Inc
Bus 003 Device 004: ID 058f:6366 Alcor Micro Corp. Multi Flash Reader
Bus 003 Device 003: ID 0461:4d51 Primax Electronics, Ltd 0Y357C PMX-MMOCZUL (B) [Dell Laser Mouse]
Bus 003 Device 002: ID 046d:c52b Logitech, Inc. Unifying Receiver
Bus 003 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Goggling the USB ID's you can find which one is the Bluetooth device in my case 0cf3:3004 Atheros is in fact the Atheros AR3012 Bluetooth device.
Then if you perform a dmesg output I could find two lines saying
[ 13.946058] Bluetooth: Patch file not found ar3k/AthrBT_0x01020200.dfu
[ 13.946058] Bluetooth: Loading patch file failed
Goggling again AthrBT_0x01020200.dfu the problem is solved installing the firmwares package linux-firmware
sudo apt-get install linux-firmware
which install the firmware file /lib/firmware/ar3k/AthrBT_0x01020200.dfu.
That solve the problem.
sudo apt-get install blueman
.lspci
into your question please.