I had the exact same problem. But resolved by chatting with Garmin Support. you have to connect Bluetooth via Garmin Connect app instead of iPhone Bluetooth settings. Try this:
-- on your iPhone:
open Garmin Connect app. at the lower right corner, hit the "More" button --> "Garmin Devices" --> "Add Device" blue bar at the bottom of the screen, --> "Forerunner 35".
-- on your Forerunner 35:
press the menu button (lower left), scroll down to "Settings" -->"Bluetooth",--> "Pair Smartphone". It will show a pairing code which you can enter to your iPhone
Now the connection should work.