I'm having the same issue with one of my bluetooth devices (earbuds). I regularly use 3 other bluetooth devices, and haven't had any issues with those connecting. The one device however, exactly as you describe.
Edit: This is on a 640, removed from slow ring back to production and updated to w10m. I didn't have any issues with the exact same headset on the slow ring build... but haven't re enrolled back to slow ring (I'm tired of having hard reset and re set up my phone every few days, which was why I rolled it back to production in the first place).