This user wasn't added to this PC. Code: 0xd0000225

So, found the root cause of my particular problem. For some reason, the Security Packages that Microsoft Accounts use were not registered on my brand new (okay, refurbished) Lenovo laptop.  For the record, that's really, really unexpected, and I bet a re-install from shiny media, or a reset on a machine whose reference image is good, would fix this.  Oh, well, that's not an option for everyone.

Still, I've experienced this on two separate Lenovo laptops within a month, so there's probably something in common there.  Maybe the Windows image Lenovo customized got corrupted, maybe it's the AV trial s/w that comes with it is removing the regkeys, who knows?

Anyway, I just added "pku2u" and "livessp" to the Security Packages REG_MULTI_SZ key under regkey HKLM\System\CurrentControlSet\Control\Lsa. 

Immediately, I was able to add Microsoft Accounts. :)

(If you already have pku2u and livessp in the list of Security Packages, of course, then this isn't your problem, and just move on. ;)

CAUTION: Don't remove *anything* from the existing list in this key, and type very, very carefully.  If you really blow it when you edit this key, you can probably brick your PC, since the Local Security Authority (LSA) is core to the system.  There's a reason Microsoft tells you not to monkey with the registry.  You've been warned. ;)

Would be great if Microsoft could provide a Fix-It script that could safely fix this and eliminate the human factor of typing in regedit...

In the meantime, if you are comfortable with regedit, this might be something to check if you hit this problem.