After a 90 minute support call with Apple earlier (and three different support engineers), I'm finally back up & running.
First engineer went through basic stuff: Reboot devices, untick "Allow Apple Watch to unblock..." - things I'd already done.
Second engineer started off by suggesting to reboot my router (!!!!!) - I explained the issue with no unlocking happened whilst on company network as well as my own - so ruled out such a thing. They then proceeded to get me to unpair my watch and iPhone - a tedious process - then pair again as a new watch (not to restore from backup).
Still no luck after all that!
The third, and final, engineer seemed to know his onions. First off we rebooted the MacBook into Safe Mode (Hold down shift when starting and let go when you see the Apple logo). You can verify you're in Safe Mode, by going to About This Mac (via Apple logo top left), then System Report. Scroll down to Software section (and click on it) on left-hand menu. "Boot Mode" should be Safe if you got it right on boot-up.
Sadly, even after logging-in, playing with the unlock your Mac option, nothng was helping.
We created a new user profile, (with Administrator rights, as opposed to Standard), logged-off and logged-on again to setup this new user. Logged-in with my own AppleID/password, then proceeded to select the unlock your Mac option.
Put the laptop into Sleep mode, and upon walking, the laptop logged-in via the watch.
So, we deleted my old "own" profile - luckily no big deal as I'd only just got the laptop yesterday so still had a lot of my usual apps to install. Then we created a new profile that would be my proper account to use - logged-off/logged-on and set it up as normal with AppleID/password when prompted.
First, we checked iCloud in Settings to make sure all was well there and my account showed. Then back to Security and Privacy to set the unlock your Mac option.
This was weird... as it seemed not to want to turn on... (spinning wheel and stating "Turning On"). After a few attempts (as well as the cannot authenticate error - engineer suggested making sure phone was unlocked and the watch had it's display showing), it eventually turned on correctly.
Upon testing Sleep/wake/login with watch we were up & running.
Quite a bit of messing around as you can see, and I'm still stumped by the fact only the Watch OS update to 3.2.2 that occurred seemed to mess things up.