You probably rebooted after uninstalling that update? Reboot (or WinExplorer restart) solves (only temporary) the issue.
Are you sure the issue is solved permanently by removing that update? I doubt it.
May I ask to all ppl with this issue, what hardware are you on? Because we manage some thousand client-pcs, and this "not implemented" error with the Windows Photos-app was only reported with one particular model (HP Elitebook G8).
What hardware are you using? And what anti-virus solution? (we're using Sentinel One)
I'm using a Dell G5 5590 running Windows 10 Pro. So far installing the legacy app seems to have worked, though it would be nice if MS could both ackowledge, then fix the problem with the current Photos app. FWIW I run AVG Internet Security for AV.