Finally fixed it! What didn't work, not surprisingly, was the MS Fix-it. Downloaded and ran it, and it said it's not for this version.
Then, I used the Win7 forums tutorial on resetting Windows Update with the two downloadable batch files. I ran the first to remove the history -- it worked. I then ran the second to reset WU -- it also worked.
When I rebooted, there were no updates in the history, I did a check and this time, it ran and found 8 updates. I applied those, rebooted, ran a second check, and this time, it found no updates.
So, it looks like I'm good to go with WU again.
(I'm posting this from my Win8 CP session).