I think you may have to reset the gear S too...
You
must reset your Gear S when you either reset your phone, delete a linked Gear S via Gear Manager, or uninstall and reinstall GM on your phone. If you've chosen to back it up (in GM settings) when you reconnect it it'll restore most of your stuff from the host device. If you hard reset your phone there's nothing to restore so you'll have to rebuild your Gear S manually. As for updates, if it's for GM go in to Samsung Apps on the host device and take the update. If it's a Gear s/w update try accepting it after your Gear's properly reconnected to the host device.
Tip: When you're hard resetting your Gear always go in to BT settings and manually delete its profile first. The first thing GM does when connecting to a Gear is setup a BT connection and it can cause problems if one already exists,