I have the intermittent disconnect issue as well with a Note 5 and Gear S. It started several weeks into owning the phone, after a few updates, but not right after. Even RMA'd a Gear S thinking it was the problem because I somewhat reproduced the issue with a Tab 4. If you have a Samsung tablet that can install Gear Manager, please try it out. Leave it connected for at least a day and play with the watch a lot. That seems to trigger it.
Another strange thing I noticed is after giving up for a while or trying the new watch I got, it stayed connected nonstop for the first several hours before beginning the disconnect/reconnect cycle. Could the issue involve how long Bluetooth is enabled on the phone? Is it some sort of sleep setting or overheat protection?