I'm starting with some background so the question can be answered in-context. Apologies if I veer into too much storytelling.
Pre-Cataclysm Setting: A fantasy civilization, essentially only humans, in the middle of a magic-fueled industrial revolution. (Rather than fossil fuels)
The civilization exists in a quite limited habitable area, about 30,000 square miles, surrounded by a larger uninhabitable region, which is inherently dangerous. People can survive in the uninhabitable region if they can protect themselves from beasties, but they can't grow food, even with magic, so they can't be independent.
Population centers tend to be in the middle of the habitable region, with frontier towns on its borders. The total population is around 10 million people. Everyone has the capacity to do magic, but it's difficult enough that only about 1 in 5 people actively practice magic.
If other habitable regions exist, they have not been found yet.
The Cataclysm: For reasons that are intentionally not fully explored, everything involving magic goes very wrong, pretty much all at once. It's worse where there's more magic, and generally worse near the middle of the habitable region than on the edges. In the less affected areas, it's mostly explosions, toxic gasses, earthquakes, and the like. Towards the more affected areas, things work their way from biblical to eldritch, culminating with some places simply ceasing to exist. (For example, a city set between a forest and a river suddenly becomes a river running through a forest)
Post-Cataclysm Civilization: The frontier towns on the edges of the habitable region avoid the worst of the cataclysm, and hunker down to weather its consequences. The worst effects die down in a matter of days, but it's decades before it's actually safe to travel. Several towns die off in this time, but enough are able to sustain agriculture that, about 100 years after the cataclysm, roughly 10,000 people have survived.
As people start to travel again, they find that the habitable region is fully habitable again, with very little evidence of the cataclysm having ever occurred, beyond the total absence of humanity. There are barely even any remnants of the pre-cataclysm civilization, and where they exist, magic is still pretty apocalypse-y, so they haven't been successfully explored yet.
Setting Goal My intention is for the vast majority of the past civilization's culture and technology to be fully lost, with each surviving town having very different cultures and beliefs that emerged, but no true connection to the society that came before. The only throughline for the towns will be a pretty reasonable distrust for magic.
I'm not sure how reasonable this is, given the events and timeline. When discussing this setting with a friend, he got pretty fixated on why everything was lost, and I don't have great answers.
Poking through past questions and answers, I see references to minimal viable populations, which the towns get close to, individually, but the towns that survive are probably in the ballpark of 500 people. Looking at posts about losing or recreating technology, I see a lot about how losing technological infrastructure can set a civilization back decades or even centuries.
I didn't find much about cultural changes, particularly changes in cultural institutions, such as religions. I don't really want to map out the entirety of the past civilization's societal structure in order to decide what would and wouldn't make it because, well, the point is that pretty much nothing makes it.
I'd appreciate any advice anyone has on justifying the extreme loss/changes in culture in this post-magical-apocalypse setting.