I have a Nexus 6 and a LG Watch Urbane, both stock. They have been paired since birth, until yesterday. Since my phone got the April update via OTA, neither device finds the other on Bluetooth. I have hard booted both devices, twice. No bueno! I think that I have solved the problem, by doing a factory reset on the watch. It was a pain, but not as bad as doing a factory reset on a phone.