When adding new light to existing lights, only 1 or the other works
There's a serious defect in this installation.
All the places where cables come through a knockout hole, you can't do it like that.  You need to fit a cable clamp.

For the cables entering on the right, there's a special bracket that comes with this style of box that provides a dual cable clamp. I gather you removed that for this initial hookup; make sure it gets back on.
Where's power coming from???
My initial impression, based on your symptom, is that you tried to use that diagram of yours, except you attached it to a switch loop instead of to a power source.  A switch loop may seem like a power source when the switch is off; if you decided it was a power source because of testing, test again with the switch on.
The only saving grace I see is it appears the older black cable is a /3 cable.  It might be black for always-hot, white for neutral, and red for switched-hot; that is a modern type of switch loop that you would be able to use effectively.  However you seem very unclear on the function of the various wires.  We'll need to do more work to identify them.
Honestly, I am getting the impression that this setup is a former 3-way switch group.  This might be saveable; but there's another question: which switch did you just eliminate?  Some switches are required by law.  Every room must have a switch in the usual location (you know where to grasp when you enter a darkened room for the very first time, right? That's not by accident). Further, stairways MUST have a switch at top AND bottom.  You can't eliminate those mandatory switches.