Try connecting the device via bluetooth without the connect app first. Then connect your device with the Connect app. I had the same deal going on and the phone was finding the watch before Connect did. Once I connected it without using the app it paired no problem.
