This started acting up about 3-4 months ago. I even considered buying a used one on our version Craigslist (Blocket.se), but actually made it “reconnect” again - for a while - by trying your suggestion. Also I “clicked through” the options (Jackhammer, Mario, Nudge etc.) several times (middle button) and now it works. For a while.
Otherwise I still love this watch. Even more than the Gear S3 which I used with my Galaxy S7.
Weird. But true.