I tried basically everything on here and here is the only thing that worked for me: Reset my Apple Watch (delete everything) and deleted the Apple Watch app from my iPhone Had my boyfriend use his iPhone to do the update. This was the only way I was able to update it without getting the internet error message. when it was done updating, I unpaired it from his phone and paired it to mine after re-downloading the app . It worked! Good luck!