Two hot wires feeding a gfci installed ten years ago just started popping? Replaced gfi figured out a bigger issue
NEVER "just try random things"

Why not? Think about it.  You are trying things until when?  Until it works. The problem is, there are lots of combinations that will work that will kill you. 

No. Only do things based on knowledge and understanding.  If you don't have enough, get more - either by reading more about electricity, or doing more testing, as needed. 

The first rule of hooking up GFCIs

Hook up the LINE terminals ONLY.  Fully test.  When perfect, then hook up LOAD.   And if hooking up LOAD results in a trip, then you know LINE is correct and so you know your problem is on the LOAD side. 

The second rule of GFCIs is "Never use LOAD unless you know exactly what you're doing." Instead, pigtail all wires to LINE, or double-tap LINE if the GFCI supports it (most do).  Most people have no earthly idea what LOAD actually does... They just know they have 2 extra wires, and look! Two extra screws under that warning tape I didn't read.  Most GFCI trouble comes from people using LOAD thoughtlessly or by default.

Your particular situation

First, the thing about the red wire applies to circuits that are not like yours.  Don't worry about that.  

Yours is likely to be an "accidental ring circuit" (rings are a UK thing, not allowed anywhere else), where your circuit travels a big loop from the breaker through the house and back to the breaker, but in this case it's another breaker.  This was a wiring mistake. Wiring layouts are supposed to be "tree style" and never loop back on each other. 

If you are able to map this "ring", look for an appropriate place to break it, so it is once again two circuits.  There may be an obvious place to do that once you get into it.  You are likely to uncover an obvious wiring mistake, which you can then just fix. Or maybe  two receptacles side by side in a double box (4 sockets) - wouldn't it be nice if they were served by separate circuits?  Anyway, you break it there - take one hot-neutral pair and cap them off. 

While you're doing this, be on the lookout for separation of hot and neutral.  Neutrals must stay with their partner hot, and not cross over to the hots and neutrals of other circuits.  That is because neutrals don't have fuses even though they can burn up just like any other wire!  Their protection depends on being fed only by their partner hot.  If you see anyplace the neutral isn't with the hot, get rid of it.  It's unsafe by itself, and also won't feed properly off LOAD on a GFCI.