Wonder if you're hitting a 2.4G/5G issue with wifi with the iPhone/Watch. Do both of your wifi networks have the same SSID?
Well I did hit that problem initially, that's what sparked the troubleshooting. I didn't get the green cloud icon when bluetooth was off. The fix for that was to use the same Time Capsule SSID for both 2.4/5 GHz, "forget" and re-enter the network on the phone. After a few restarts the green cloud icon finally kept showing after disabling Bluetooth. Success in that regard.
.. And just by accident iWatch started automatically unlocking the 2015 MacBook 12" too. 100% reliable
Then I turned bluetooth back on, and "Watch not found" messages appear every time. That's the status I'm at now. Latest beta versions in use of course.
On the late 2014 iMac 5k it's different. iPhone bluetooth state doesn't seem to make a difference. Auto unlock works about every 5th or 10th time. Console talks about "Ranging Timeout" with an ambiguous error code, and unlock fails even when the Console text seems to indicate the Watch was found and is in range. It appears it will try up to 5 times before the user must unlock with a password.
I've done the usual iCloud sign out/in tricks and started with a clean slate in July, in that regard things should be fine. Watch recently re-paired with the phone.