Using my Apple Watch to unlock my Macs has worked well for me in the past, but it started failing consistently after a recent OS update. This post from the Apple Community Forums got things working again for me. Just so it doesn’t get lost, here is the fix:

1. On the Mac go into Settings->Touch ID & Password and turn off the setting that allows the watch to unlock the Mac.
2. Quit Settings, then put the Mac to sleep (close the lid, etc.). A shutdown or reboot should also work (though not tested).
3. Restart your Apple Watch and let it come up and connect to the net. You should be able to check the weather, for example. You’ll need the full network stack up and running on the watch.
4. Confirm that Bluetooth is turned on on your Apple Watch.
5. Login to your Mac, go to Settings->Touch ID & Password and turn on the setting that allows the watch to unlock the Mac (i.e. reverse what you did in step 1).
6. At this point you should be prompted for a password, then it will say, “syncing…” and will end with the slider showing that the setting is enabled.
7. Test to see if it’s fixed

Thanks @pars33ker.