I tried everything solution from all of these answers and still had no luck, but I discovered a fix that worked for me! I reset the watch to factory settings with a hard reset, then when prompted to pair the watch to my Iphone, I turned on airplane mode (while connected to wifi) and the the Iphone almost immediately began the update as normal. Hope this helps!