I had the same problem (trying to pair, but my garmin kept displaying 'connecting' for a while, and then said it failed to connect):
* I reset my garmin to default settings
* I unpaired the device…
Thank you that worked great