I had the same issue with a new Edge 1030 and an iPhone 7 running the latest ios11 beta. The following from the phone connection post above (thank you Raqballl!) worked for me me:
From Per DCR try this:
For totally re-setting connections on the Edge 1030, be sure to complete the following:
A) Remove pairing on Edge 1030 B) Remove BLE pairing on settings on phone C) Remove BT pairing on settings on phone D) Delete Edge 1030 from Garmin Connect Mobile E) Airplane mode on F) Kill/close GCM app
Same issue here with a Garmin 1030 and a Samsung G7e. Bluetooth worked fine initially then I upgraded the Garmin software and now no Bluetooth. Starting to wish I hadn't paid ?500 for the privilege of beta testing Garmin flakey products.