Out of nowhere, the remove background button in my quick actions now does a terrible job finding the backgrounds of my photos. Sometimes it says: "Could not complete your request because of a program error." The same photos that it used to remove the background from perfectly now do not even work anymore. What could the problem be? There is an example of what is happening attached.
Like Derek is alluding to, that looks more like a GPU issue than a Photoshop function playing up. Make sure your video card driver is fully up to date and sourced from the card's manufacturer.
You mentioned the same images that once worked OK now having the problem. You didn't say if it is the same computer hardware. It has been known for a big Windows update to arbitrarily change the video card driver to a generic driver from Microsoft, which causes all sorts of issues.
If we know what OS version you are using, we'll be able to point you at the approriate help pages.