That usually the fault of the echo canceler at the central office, but if you changed carriers (changing MVNOs but keeping the same carrier means going through the same central office if you're in the same area - which could still mean a problem with the carrier) it would be the fault of the phone,but not something that's easily fixable.
So ... if you're still on the same carrier, go into a carrier's store
with the phone and let then hear the problem - they can call engineering and get it straightened out. (And probably make some of the older engineers learn something they'll never see again - it almost never happens.)
If you changed carriers, the first thing I'd try (after a full backup - see
Backing up an Android Device) is reflashing the ROM (see
[Samsung] How to flash Stock ROM via ODIN).
The only other possibility is something causing an acoustic echo - the incoming sound is feeding into the mic - but since it still happens with earbuds, that can't happen unless you take one of the buds off and hold it against the mic.
