Hi joao.parreira,
Please make sure to update to the latest firmware version WW-16.0615.1912.115.
Please try resetting your network settings and try again. (Settings > System > Reset options > Reset Wi-Fi, mobile & Bluetooth)
If the problem still appears, please provide the Bluetooth headphones brand and model that cannot be recognized.
Thank you 🙂