My 645M updated a couple of days back and yesterday my watch and my phone lost bluetooth connection and would not return.
This morning I have:
1. Removed my device from Connect and attempted to re-pair - pair failed.
2. Restarted both devices and then same steps as 1 - pair failed.
3. Factory reset my watch (and yes, I did, not a soft reset), deleted connect and reinstalled - pair failed.
4. Repeated step 3 with a debugger open. The following messages are given when pairing is attempted:

There appears to be some authentication issue between my watch and my phone? As in something now being sent across?
Short of factory resetting my phone, which I'm pretty loath to do, what else can I try? Or has something been missed before the previous firmware update was pushed out?