A recommended fix for this issue can be found below:
1. Go to www.garmin.com
2. Click Login form the upper right corner of the page
3. Under Profile click Products
4. Locate the device that you would like to remove
5. Click the Remove
6. Confirm by clicking Yes
7. Please could you then perform a Default Restore and then try to pair again.
If you are using an iPhone, you also need to remove the device from your Phone's bluetooth settings before re-pairing. (Also consider reinstalling the GCM App on your phone)