Ok I got it work!!!
This was about the 4th or 5th time I tried it.
Here's the deal. I DID NOT REBOOT THE COMPUTER.
I followed these exact steps.
1. Open "Keychain Access"
2. In "View", enable "Show Invisible Items”
3. Search for "Auto Unlock"
4. You should see a whole bunch of application passwords for "Auto Unlock: XXXX's ..."
5. Select all records and delete (this will reset/disable auto unlock on other Macs if you use multiple Macs)
6. Whilst still in "Keychain Access", search for "AutoUnlock" (no space)
7. There should be 4 entries for "tlk" "tlk-nonsync" "classA" "classC"
8. Select 4 records and delete (don't worry if they re-appear, the system repairs this automatically)
9. Open "Finder" and navigate to "~/Library/Sharing/AutoUnlock"
10. There should be two files "ltk.plist" and "pairing-records.plist"
11. Delete both files
13. Open "System Preferences" and try enabling auto unlock. You may need to enable it twice, the first attempt will fail
Those were my exact steps. If everything is working, in your Keychain you'll see an Auto Unlock - Your Watch Name.... Previously, that never showed up. Notice how it's missing step 12. Step 12 was when I rebooted the computer the first 3 times. The only time it worked was when I didn't reboot the computer.
The other thing is, previously, my ltk.plist and pairing-records.plist would be empty every time I tried it. This time, I saw information (encrypted I think), in them.
Hope this helps someone.