I have had very similar results, Android phone (Nexus 6P) and trouble connecting. The app is really unreliable about connecting to the lock. I wait and eventually I restart my phone which usually gets it connected. Sense is really unreliable also. I've stood outside my door staring at the app waiting for it to connect so I can manually press the unlock (or lock) button, but eventually pull out my key. Once inside the house i'll get the message that sense successfully unlocked my door.
I do have a bridge though, which is another source of headaches. It never seems to work quite right no matter where I've put it in the house. Both the bluetooth and wifi are listed as good. A lot of times the app will show that it's connected to the lock via wifi, but when I press lock or unlock it'll tell me the bridge is down and to connect via bluetooth but the wifi/bluetooth toggle button wont work.
My wife has the same issues using her android phone as well.
I dont know if I should piggy back here or start my own thread.