I've been having an issue when my fenix 3 would lose connection with my iphone 6 several times a day and when i went into bluetooth there was a spinning gear and i couldn't turn it on or off from this menu......i couldn't even unlink any associated bit of kit. I tried the usual sliding the phone into and out of airplane mode but this would only switch the wifi on and off. I tried hard resets, restired the phoen several times and then upgraded the iphone IOS 9.3.3 and even beta tested the ios 10!!! I went to the iphone genius bar and they tried all that too.
Long story short is that it is (in my opinion) a Garmin Connect app issue.
The simple fix i have found is just to open the connect app. go to your device and it'll say that bluetooth is not on etc. Close the app and swipe up to remove it from multitasking. Then reopen it. Your device should now be connected. Crazy really.
Hopefully the developers will see this and sort it.
Anyone having the same issue please post and get some weight behind it.