Headset wird nicht gefunden

Seit einigen Tagen besitze ich das Arc S und habe nun das Problem, dass ich mein Bluetooth-Headset nicht mit dem Handy verbinden kann. Das Headset wird einfach nicht gefunden, auch nicht, wenn ich in den BT-Einstellungen nach Geräten scannen lasse.

Woran kann das liegen bzw. wie kriegt man das hin? Das Headset ist von Plantronics und hat mit meinem vorherigen Handy (Acer Liquid) problemlos funktioniert.