The bad news: It is a real code and safety issue. While extremely unlikely to be a problem with your refrigerator & freezer - i.e., they normally use a small fraction of 15A and if they "go bad" and overload then they'd probably use far more and trip even a 20A breaker (i.e., very unlikely they'd end up "bad" at 16A - 20A), there is still a real problem. Let's say you decide to plug in some power tools that draw 12A (generally equipment designed for use with a 15A circuit will be designed to 80% of the capacity) and the refrigerator and freezer are running at the time (i.e., compressors actually cycle on) - now you'll end up close to 20A total but the breaker won't trip. Do that for long enough and your 14 AWG wires will overheat, potentially starting a fire.

The good news is there is an easy fix. Your problem was NOT that you needed a 20A circuit. Your problem could have been either "refrigerator with a real ground fault and the GFCI doing its job" or "old GFCI that had electronics that were a little too sensitive to the old refrigerator's not-a-ground-fault problems". Since replacing the 15A GFCI (relevant) and 15A breaker (not relevant) solved the problem, the solution is:

• Put the 15A breaker back. (Actually, you said fuse, so put the 15A fuse back - but fuse or breaker is irrelevant here - the problem was the GFCI).
• Replace the new 20A GFCI/receptacle with a new 15A GFCI/receptacle. Try to get the same brand/model (except 20A instead of 15A), as the difference might be that the old one was "old technology that couldn't handle the refrigerator properly" but might also be that the old one used slightly different technology from the new one, as each brand is a little different.

Technically, the 20A GFCI is not in and of itself a problem because the overcurrent protection is provided by the fuse or breaker. But it needs to be replaced because the receptacles with the GFCI are 20A receptacles, which could lead a future user to plug in a 20A device (e.g., a heavy-duty power tool) and get either nuisance trips/blown fuses (annoying but safe) or overload the wiring (not safe). So the 20A receptacles on a 15A (14 AWG) circuit are themselves a code violation.

The bad news: It is a real code and safety issue. While extremely unlikely to be a problem with your refrigerator & freezer - i.e., they normally use a small fraction of 15A and if they "go bad" and overload then they'd probably use far more and trip even a 20A breaker (i.e., very unlikely they'd end up "bad" at 16A - 20A), there is still a real problem. Let's say you decide to plug in some power tools that draw 12A (generally equipment designed for use with a 15A circuit will be designed to 80% of the capacity) and the refrigerator and freezer are running at the time (i.e., compressors actually cycle on) - now you'll end up close to 20A total but the breaker won't trip. Do that for long enough and your 14 AWG wires will overheat, potentially starting a fire.

The good news is there is an easy fix. Your problem was NOT that you needed a 20A circuit. Your problem could have been either "refrigerator with a real ground fault and the GFCI doing its job" or "old GFCI that had electronics that were a little too sensitive to the old refrigerator's not-a-ground-fault problems". Since replacing the 15A GFCI (relevant) and 15A breaker (not relevant) solved the problem, the solution is:

• Put the 15A breaker back. That takes care of the main safety issue.
• Replace the new 20A GFCI/receptacle with a new 15A GFCI/receptacle. Try to get the same brand/model (except 20A instead of 15A), as the difference might be that the old one was "old technology that couldn't handle the refrigerator properly" but might also be that the old one used slightly different technology from the new one, as each brand is a little different.

As far as why a new GFCI 15A didn't work either? I'll bet it was a different type. If the new 15A and 20A that you have tried so far (15A didn't work, 20A did) are the same brand and model (except for current rating) then there is something really strange going on. But the 15A was brand X and the 20A was brand Y then that could easily explain it.

Technically, the 20A GFCI is not in and of itself a problem because the overcurrent protection is provided by the breaker. But it needs to be replaced because the receptacles with the GFCI are 20A receptacles, which could lead a future user to plug in a 20A device (e.g., a heavy-duty power tool) and get either nuisance breaker trips (annoying but safe) or overload the wiring (not safe). So the 20A receptacles on a 15A (14 AWG) circuit are themselves a code violation.

As Harper noted, setting up dedicated non-GFCI receptacles is a reasonably safe and likely (but not guaranteed - AHJ-dependent) code-compliant solution.