I realize this is an old thread but I had the same issue, found this thread, spent a few hours and found a solution. Then got another pi and completely forgot how to fix the issue, and had to search again. Figured id post the solution here this time.
Found a solution here: https://www.raspberrypi.org/forums/viewtopic.php?f=66&t=171456
The issue is with BLE devices. The following from jonathancorrin worked for me:
Reboot the pi
open terminal window and type the following lines:
sudo hciconfig hci0 down
sudo hciconfig hci0 up
Press the discovery button on the bluetooth device, the device should popup >in the terminal along with its bluetooth address, then type the following >where X is the bluetooth address :
A dialogue box should popup stating that the bluetooth device would like to >connect, press connect and then the ok button on the next popup.
I did however have to reboot my pi an additional time after these steps.