This issue is still happening. I have an iPhone X running on latest beta release and it's been a while I used my Apple Watch 4 series. When tried to pair the watch, I was not able to proceed further to pair as I see "Unable to Check for Update" error screen with Start over and try again options.
Do we have a tracking ticket for this bug?