I would love to be the first snarky reply to say: You should get an Apple Watch instead.
But I'll add something hopefully helpful ...
Assuming you're not on beta.
Try also setting watch up 'as new' one time and do not restore watch. That may help. It did for me on beta release.
Resetting Network on phone can't hurt. I have read in some articles to turn the watch to airplane while switching phone network settings. I have never needed to do this.
Does this happen while having phone and watch in close proximity or across the house etc?
If it happens while close: does your phone have trouble connecting/stay connected to other Bluetooth devices? If not maybe take the watch back to get it swapped for new one.
If it happens while across the house (same WiFi scenario), make sure your phone is not in faster 5GHz WiFi. The watch doesn't support it. Once I did that I get the green cloud and can connect on same WiFi off BT.