Yo tengo el Edge 820 y a veces cuesta que enlace, pero diría que es más problema del Garmin Connect que de la conexión entre el tfno y el GPS.
A mí me cuesta enlazarlo para descargar el recorrido hecho, suelo apagar y encender el Garmin y conecta sin problema.