NO bluetooth devices were working on my computer, suddenly (yosemite).
– Hold down the power button continuously. Check.
– Remove batteries, turn off bluetooth, add batteries, power up, turn on bluetooth. Check.
– Fresh batteries. Check.
– Distance / remove all other BT devices. Check.
A good old restart fixed my problem instantly. Instant pairing request / detection of my devices.
It looked to have installed an update on startup, so it was a much needed restart.