Got mine yesterday, and it’s exhibiting similar behavior. The phone (Galaxy S4 not rooted) can find and pair with it, but the application will not connect.

It previously worked until I decided to put it to sleep, since coming out of hibernation…the behavior above.

I also get the password request whenever I unpair and re-pair. In my case, the password turned out to eight zeros (00000000). I tried four (0000) and it didn’t work.