i had the same problem, but my phone(with android 7.0) has a settings funtion that is responsible for managing the application permissions. There you can enable all the watch related apps and afterwords you can re-connect your watch.
settings > permissions manager > allow the watch apps to start
It worked for me!!
Installing the apk of those 3 apps helped my gear S3 frontier connect to my note 8 running one ui beta.
Prior to doing so, I didn't have the gear s plugin and the Samsung accessory service apps. And when I went on Google Play, it said that the previous apps were not compatible with my device.
Note 8 isn't synched with my gear anymore as well. Very frustrating, I've done all the regular troubleshooting (clearing cache, memory, uninstall, etc). This only happened after the last software update. Please fix, Thanks
I cant wrap my hands around how Samsung doesn't seem to see this as a huge issue.
No statements from the company about it, no updates as to when it will be resolved. Is it really that hard for a company to put out a press blast acknowledging the issue and what they plan to do about it?
My faith in Samsung has totally gone in the crapper! I will never buy another one of their products or advise anybody else to do so!