Is this something that you think would fix itself with time, or am I better off just starting a new game? Perhaps on a different difficulty level?
Usually it does resolve itself and when the AI player gets to the point that it's rolling again, it's very fast to spread. Some AI's just get the right circumstances for the AI as it is programmed to work wonderfully. Others, less often, get stuck on something sometimes. Just as in RL, I suppose, not all civilizations were winners. Not all sought to expand much either. But there should be some that are growing like weeds as well somewhere. If a game shows a problem with this all around, then there's certainly some need to look at that particular save.
But if I understand you correctly, what is likely happening here is that the AI is/was trying to build units to escort the tribes but other things have taken priority due to various flags. And because it doesn't have the right escort units for the tribe, it's not sending them out at all.
I'm saying that's one likely reason. There's a lot of potential places where the mission to settle can get bound up in a bottleneck of circumstances. Even players can fall victim to this and be delayed, but players can see a bigger picture than any AI will ever be able to and juggle far more variables in play and get a better determination of priorities for that reason (while the AI is going to be a lot better at seeing immediate details with complete clarity and accuracy than a player likely would.) So I guess as a designer, at the moment my goal is to make sure that it USUALLY works. If you are on a particular option set that is causing larger trouble, that's worth some investigation, so it could be good to review options that might be an issue. I'd need to see your save to look through that and flag a few possibilities. There are some other very good contributors here at doing that as well. Joseph comes to mind, though I know he's not currently likely to want to look much into it. My time is very spread thin at the moment and looking like it might stay that way for a while, so I may be willing to look at the options and theorize a bit but probably not currently wanting to look deeply into the code to see exactly what's stopping them. The problem is not endemic to most games it seems at the moment.
I know one thing that stops them - if they want to expand via navy, requiring transport to another continent. There's a complex bug in that somewhere that has the settlers sit there for a while waiting on transportation that never seems to come (or just takes a very long time to put the mission together) and since the settler has been trained, it keeps others from being trained for a bit because the nation thinks it has what it needs to grow. This is hugely complex and I don't have the time to resolve it atm.
For a number of years here I have been stressing myself out looking to perfect the mod while making headway with design plans. I've put many thousands of hours into modding. I'm beginning to feel a need I often feel during spring and summer to not let it be so consuming as it has been. I promise I won't stop working on this mod but I can't just dive into every flaw found, even if it appears fairly critical. I'm tiring of being the primary mod doctor. I'll be taking on tasks like these with a very gradual patience, chipping away at it now and then as I feel the desire to. So by all means, upload a save and I'll take a look. At some point.