The correct fix to this Microsoft problem was to boot into Safe Mode with Networking.
Once in Safe Mode, reboot to regular mode. Problem solved.
(The reason it also worked when using the Avast removal tool is because it boots you into Safe mode and than back into regular mode.)