had this problem too.. I had to install a fimware on my BT620s (if you can believe that : your headphones also need an update!). It helped a lot to sync it with my P2. I still have the occasional connection failed message, mostly when I pair my headsets with another device. They seem to "hang" to the last connection, so I have to reset them by plugging and unplugging them 5 or 10 times (I use the usb charging cable). It's a pain, so now I only pair my BT620s with my P2... Hope it helps!
ps : you can maybe still find the firmware update on jabra's site, under the BT620s page. Good luck!