Replacing 2-prong outlets in basement - existing wiring has two hot wires, one neutral?
MultiWire Branch Circuit
What you have is a MultiWire Branch Circuit, or MWBC. That is a neat trick that lets you get double the total power, with only 50% more wire (3 wires instead of 2). If you look at your outlets, you should see that the tab on the hot side which normally connects the top and bottom receptacles has been removed. That separates them into two separate circuits as far as the hot wire, but they share the neutral on the other side. In fact, the neutral only carries the difference between the two hots instead of the sum of the two hots, provided the two breakers involved are on separate poles. You can verify that the two hots are on separate poles by checking the voltage between them. You should have a nominal voltage of 240V between the hots with 120V between each hot and neutral. If you get 0V between the two hots and 120V between each hot and neutral then you have a BIG problem.
CORRECTION Rereading your description, it appears that instead of a split in each duplex receptacle (tab removed) the split here is some duplex receptacles on one half of the MWBC and some on the other. The principle is the same and the GFCI issue is the same.
The trick to making an MWBC work is landing the two hots on opposite poles. A typical circuit breaker panel will alternate between the two poles. This allows for 240V breakers for hot water heaters, dryers and other large appliances. It also allows for an MWBC. Note that if the two hots are placed on two breakers that happen to be on the same pole (e.g., regular breakers but not next to each other or 2 1/2-size breakers that replaced one regular breaker) then you will end up with:

0V between the hots (not in and of itself a problem, but a symptom - and an easy way to check that an MWBC is correctly wired)
Current on neutral is sum instead of difference - this is the real problem as you could have 40A going on a 20A rated wire.

In addition, an MWBC must have common shutoff so that you can't turn off (in your example) the black wire to work on a receptacle without also turning off the red wire. When you turn off a breaker to work on a circuit, you normally are trying to get everything you might touch at the time to be dead - so turning off the pair of breakers at the same time is critical. Using a typical 240V breaker - which is really a pair of 120V breakers but designed to trip at the same time - is the easiest way to do that.
GFCI vs. MWBC
The problem with GFCI on MWBC is that GFCI depends on &quot;all hot&quot; == &quot;all neutral&quot;. Since most ordinary 15A and 20A receptacles are NOT on MWBC, most (possible all) combination GFCI/receptacles do not support MWBC. One reason is that a typical duplex receptacle has room for 4 wires (not counting ground): incoming hot, incoming neutral, outgoing hot, outgoing neutral. But those same 4 connections can instead be used for incoming/outgoing hot 1, incoming/outgoing hot 2, incoming neutral, outgoing neutral - and you have a setup similar to that. That works because the incoming and outgoing wires (e.g., 2 wires for hot 1) can be connected together.
A GFCI can not have the incoming and outgoing wires connected together. A GFCI needs to compare the outgoing (usually called &quot;LOAD&quot; on a GFCI) hot and neutral. Mixing in the incoming power (from the panel) messes that up. So there just aren't enough connections to make an MWBC work.
However, there is a simple solution: Use a breaker instead. Replace the existing double-breaker (it should be a double-breaker, but it might be two separate breakers which is unsafe as noted above) with a double-breaker with GFCI. That is designed to handle an MWBC or any other 240V load and provide GFCI protection. It is a little different to hook up as it connects to neutral as well as the 2 hots, unlike a regular breaker that only connects to the hot wires. You must use the right type of breaker - post a picture of the existing breakers and the pros will figure out what you need.