Hey!
Had a similar problem with my Edge bike computer, eventually I realised that Garmin devices will only connect if the Garmin Connect keeps running (at least in the background).
This wasn't a problem with my previous phone (Nexus 5), GC started when the phone was turned on and kept running in background, however, MIUI seems a little more rigorous in its memory management and likes to cut background apps it doesn't need.
My Edge connects just fine if I keep GC open on the phone, but the connection is if I try to close the app or press the "X" button in the multitasking window. I can't seem to find a way to keep GC running permanently the way it did on my Nexus... *sigh*...