This can be a result of multiple things, so please make sure to do the following troubleshooting:

1. Make sure you have Sleep as Android Gear Addon installed on your phone
2. It can happen that the addon cannot be started by us if it was force stopped previously. In that case please go to https://play.google.com/store/apps/details?id=com.urbandroid.sleep.addon.generic.samsung on your phone (using the Play Store app) and tap on “OPEN”.
3. Opt out of any battery savers that you might have on your phone, for all involved apps (Sleep as Android, Sleep as Android Gear Addon, Samsung Accessory Services) – to find out how to do that, please consult dontkillmyapp.com
4. Samsung Accessory services sometimes misbehaves and prevents connection to the watch for 3rd party apps. Please uninstall and reinstall it.