I had this behavior as well. I had to configure each depot combinator to not require the train to return to the same depot. Once I'd cleared all the blockages by sending trains out to random places (with ctrl-click), everything got smooth again.
I don't know how the problem started, logically, unless there's something about the train remembering its depot that I don't understand. Every train in my base has its own depot, so I'm not sure how a second train would be sent to a depot .. Ok I have a thought. Perhaps this is what happened:
I had trains in-flight when I launched with the new patch. Train 1 parked at depot 1. Train 1 dispatched. Train 2 finished its route and parked, also at depot 1 (because its schedule was pre-patch). When eventually both trains needed to be parked, whichever came in last would sit behind.
I think that makes sense. If I want to use that toggle on a running megabase, I think I'd need a way to call all the trains home before configuring it to the "require" setting.