Hey guys.
Just wanted to help you guys out with this issue. I came across this check for update issue around 6 months ago and gave up entirely (my watch collected dust since then).
Decided to give it another try today - and it fricken WORKED.
What I did (following some steps from the first page)
Signed out and in of icloud on my iphone (uninstalled and reinstalled apple watch app)
Reset/erased contents of apple watch.
Turned on apple watch.
Turned on iphone + signed back in.
When setting up my apple watch - I DID IT MANUALLY (Don't use the camera to sync the watch and your iphone, instead use the serial code).
Voila