I have a much lower tech solution. My watch was out being repaired and I just got it back. I tried to set up and got the same error as all of you. Probably tried to turn everything off and back on 10 times. Before wiping or re-installing anything I tried one more thing... I left BOTH the phone and the watch connected to their chargers for the entire pairing and set up without disconnecting them for even a second. Worked without any further problems. Weird.