Why doesn't my 3-way light circuit work in some configurations?
First, be clear on how 3-way circuits work.  Now it's really hard to be clear in a diagram or junction box full of Egyptian spaghetti (red white black green).  So we'll fix that -- thusly.

Here is a basic 3-way diagram.  Now this doesn't tell you anything that jsotola's diagram doesn't, except for one thing -- we are adding color to designate wire function.
Black and white are hot and neutral, of course.  Red is a traditional/common color for switched-hot.
The two travelers are different, but interchangeable, so they can be the same color without harm - in this case yellow.  Feel free to use purple or blue if you prefer, just as long as it's unlike anything else in the box.
You can't buy /3 cable in yellow-yellow-white. So we end up using the stock black white red.  And I say re-mark wires using colored tape to designate function.
Based on OP's description and comments, it sounds like there are two /3 cables and two /2 cables coming into a junction box like this:

Here I show the usual black-white-red cable colors, but I also &quot;use tape&quot; to re-mark them by function.  Boy, this makes a big difference in clarity.  This particular box didn't have a big problem with mixed colors, but some do.
Note that by OP's convention, the native-black wire is the one on the &quot;common&quot; (black screw) of the 3-way.
Now, if it's not working, it sounds like your travelers are not set up correctly.  I have a feeling you have them crossed with something else, e.g. At a 3-way for a wire meant for a common terminal.
Tip on 3-ways: look at screw colors.  The location of the common vs. other screws is completely random.  I have held two 3-ways from the same manufacturer in my hand and one of them, the common is upper left, the other, lower left.  WTH?  I've been tempted to try to collect all 12 combinations!