My AutoUnlock stopped working. In system preferences, I found the Auto Unlock with applewatch box unchecked. Checking the box just gave me the error message, "Apple watch must be signed in to icloud". The box remained unchecked. When I checked them, I found that the watch and phone are actually logged into icloud with apple id.
Tried the 12 steps recommended by stoska992 without any luck. Shut down and restarted all devices. Still no luck. Finally saw somewhere that quitting icloud worked for someone. Apple menu > Preferences > Apple ID > choose "overview" in the left side menu > "sign out". Then sign back in. That worked.
Later, the i-phone settings had a message saying "some features won't work until you sign in to icloud." When I did this the auto unlock stopped working again, but in preferences, I was able to restore it by unchecking and then rechecking the auto unlock box.
Hope this helps someone else...