No, your algorithm is at fault. Here is a blow-up of a small area of your second example:

You are not properly handling when the foreground subject is partially blended against the green background. Ideally, the original image is point-sampled. Each pixel would then represent either just the green background or just the foreground. Your input images aren't like that, and your algorithm doesn't handle it well.
The best way to deal with this is to start with pictures that are much higher resolution than what you ultimately want. That approximates the point-sampled case more, and any blended transition region will be a smaller fraction of the overall picture dimension.
Proper blue or green screen algorithms do try to deal with this case, although it gets tricky and you can always concoct cases that can fool it. Put another way, the algorithm has to essentially guess about information that is not there.
One way is to do special edge processing. In the transition region between solid foreground and solid background, you have to include some additional logic. At that transition region, you assume that any hue change from the foreground in the direction of the background hue is partial blending with the background, and then remove it. Again, this can be tricky, and it can be fooled, but most of the time it will yield more of what you think it should. Even relatively simple logic will fix the case I show above. Other cases may never be fixed to your satisfaction.
Again, the better answer is to start with a high-res original.