I'm having the same issues, on a Nexus 5X. I have bluetooth enabled, but not paired in the system bluetooth menu; I have location enabled. The watch won't sync unless I disable/reenable bluetooth.
Thanks Jim - paired in phone's settings and Garmin Connect and problem seems to occur on office WIFI only - Its possible that office WIFI varies in strength from time to time -