Encontré la solución después de volverme loco, así que la posteo.... Todo viene por Android 6.0. Haciendo esto, funciona a la primera. Lo deja por si le sirve a alguien que se esté volviendo loco como yo...
Solution:
On my Nexus 5 works:
1. Download the application from the store: Bluetooth 4.0 Scanner
2. The application needs to work a GPS enabled
3. Select the Low Energy Scan and press Start Scan
4. When you find the Mi Band, then go to Mi Fit and try pair your band
5. Finally, you can uninstall the scanner