Before I start; I by no means mean that the other possible solutions listed are not correct or that they work or not, I will share with you what has been working with me with several times with different watches and phones (a total of 13 successful fixes of this problem). Try to install, once you get the “Unable to Check for Update - Checking blah blah blah", stop and unpair your watch. Uninstall the "Watch" app from the iPhone and restart it. Install the App again and pair watch. The update should proceed with any inconvenient. Hope this helps, have a good one.