If you've eliminated all the obvious stuff, here's your likely solution: before you initiate the Install stage (and this can be any time after pairing/registering for a new watch, or during the download, transfer, or preparation stages of the update), separate your phone and your watch by several meters, while staying on the same WiFi circuit, or turn off Bluetooth on your phone. The two devices will shift from communicating with each other via Bluetooth to communicating via WiFi, and that's the key to getting around this issue. At the crucial verification stage, if the watch is close enough to the phone to be able to connect to it via Bluetooth, it will do so and then generate the "unable to connect to the Internet" error. If it's not connected to your phone via Bluetooth, it will instead use WiFi to do the verification, and things will proceeds as you expect.