Hopefully this should resolve it:

Make sure you completely unpair the headphones, and then make sure you remove the entry for the
Unpair/reset the headphones (at the headphone end), do whatever it says in the headphone manual.

Remove the entries from the
Status-Bar -> Bluetooth ->Devices.

If an entry remains in either device it can cause the two to occasionally have problems - thinking that they should be communicating with a key that's been set already.

If all else fails, maybe a reflash would be useful. And some sort of hard reset on your headphones since its hard to be sure which is causing the problems.