The last firmware update to the S (April or later, depending on your carrier) was supposed to fix that.
I would try reboot the watch first, unpair/repair the watch if the reboot doesn't work , clear data in the Gear Manager next if need be, uninstall/install GM if it still isn't working and factory reset only as a last resort. M has been reported as having Bluetooth issues with more than just smartwatches.