I have the same issue. If you switch iPhone 6s Plus off and on then Watch doesn't want to connect to iPhone.
Bluetooth works perfect at iPhone as I have PowerBeats3 connected and playing to iPhone.
You can pair the Watch and iPhone again but again when you will restart your iPhone you will lose your Watch.
All steps described above don't help. A lot of restarts of Watch and iPhone. Airplane mode everywhere. Dancing with a tambourine. Nothing helps.
I'm really tired of this mess.
The most interesting thing that you can switch off Bluetooth on your iPhone, then switch off your Wi-Fi.
Then you turn on Airplane on Watch and see that the Red icon saying you are disconnected from iPhone.
You wait for 30 seconds and turn off Airplane and...
Watch says you are connected showing you the green phone icon.
But as you remember you have turned everything off on your iPhone so there is no place Watch can connect to.
Another interesting thing is when you have you MacBook Pro.
You can unlock it with you Watch.
When this trouble happens (Watch lose iPhone) you can't unlock your MacBook Pro.
But if you will begin to dance with Airplane mode on your iPhone then suddenly after several tries (as I understand after some information exchange between Watch and iPhone your MackBook Pro begins to unlock again with your Watch.
Also you see at you Watch down menu that they see in AirPlay button your PowerBeats3.
This clearly says that Bluetooth works on Watch (perfect or no I don't know).
All this sh** looks like a big SOFTWARE synchronisation BUG.
When Watch and iPhone see each other but for a couple of seconds and then something goes wrong and Watch begins to think that they are connected to iPhone but it is not true.
This is another fact about this one.
When on Watch you turn Airplane mode on then the Bluetooth icon on your iPhone goes Grey (like no active connection).
You turn on Watch Airplane mode off and at once the Bluetooth icon on iPhone flash saying there is some connection with another device.
So bluetooth looks like working.
And again you can unlock your MacBook Pro and you see your PowerBeats3.
While I was writing this post for about 30-45 minutes I was switching Airplane mode also in my iPhone on and off.
And finally as some moment they begin to see it other.
This can be easily seen if you start on iPhone the application "Watch" and goes to "General" and then "About" there you can see information like "Songs", "Photos", "Applications" suited on your Watch.
If there is no connection with Watch your will see NO information (will see "---" and not numbers).
But if there is connection you will see numbers at once.
Another way go to application "Watch" and there to "Passcode".
If when you click on "Passcode" and a new window opened you and you AT ONCE see orange text "Turn Passcode off" and "Change Passcode" and all other switches active ("Simple Passcode", "Unlock with iPhone", "Erase Data") then your iPhone is connected to Watch. But if you see "Turn Passcode off" and "Change Passcode" grey and switched not active then NO connection.
When your open "About device" or "Passcode" menus and iPhone can't connect to Watch you will see a note after some 20 seconds.
I was making a lot of experiments and I have one idea for every one!
There is such Widget called "Batteries".
If you add it to your Widgets and you have more then one device connected to your iPhone then you will see the information about Batteries of those devices along with iPhone battery.
For example I have PowerBeats3 and when I turn them on I begin to see Batteries status of my iPhone and PowerBeats3.
But!!
Widget "Batteries" also shows the information of the Battery of your Watch.
If you don't see you Watch there then definitely Watch has less 20% charge left.
Put your Watch to charge and then will at once appear at "Batteries" Widget.
I know this may sound crazy, but I have a suspicion that this widget is the problem of communication between the Watch and the iPhone.
If you can't connect your iPhone and Watch then remove Widget "Batteries" from widgets list on your iPhone and turn off / turn on the iPhone.
Also when you have connection problem with Watch charge them for some time so they have more then 75% of charge.
I will make more and more experiments with this problem.
But again and again! I am 99,99% sure this is a Software problem and I am sure Apple knows about it.
Why Apple can't fix it this is the question!