I am having this exact same issue and have completed about 3 factory resets over the last 4 months. Very frustrating! I have talked to samsung, gone to best buy and AT&T, no one can help. Is there anyone at Samsung that can get this resolved? Played $800 for a Samsung Galaxy phone and $300 on a Samsung watch and now Samsung has no answers. Please help us !!
@userd3ImpzuXqs; I see you have done a factory reset for your phone. Have you tried uninstalling and then re-installing the Gear app as well?