I had my Microsoft Band2 repaired because the battery wouldn’t charge any more. When the band came back I was not able to pair it with my Windows Phone. The band worked fine – it was just the app that did not recognize any band. I tried reinstalling the app – but nothing worked.
A chat with the support helped me. The trick is to change the language of your phone – reboot – and try the pairing again. After changing the language my band showed up and I was able to pair it. After successful pairing you can switch your language back to the original value. A simple solution – but I would never have figured that out on my one.