Default [Q] Nexus 5 Bluetooth with Plantronic Backbeat Go Problem

Hi!

Anyone tried to pair up Nexus 5 with Plantronic Backbeat Go successfully?
I have tried today and it failed.
Nexus 5 cannot even see the headset.
I have tried the headset on the other phone, the headset works.
I have also tried pairing the Nexus 5 to the other bluetooth device, it works as well.

Thanks a lot.