It really depends on what type of world you're build and the type of flavor you're going for--what you're trying to get out of the setting and what the specific circumstances of the "fall" might be. Some falls can be so cataclysmic it takes ages before the environment recovers enough to support enough life for character races to start venturing into the wilderness again. Granted, that's more Post-Apoc level type stuff.
Starting it immediately after the fall can grant it a medias res type of feel, where characters begin play right in the middle of the action, as the allied forces or whatnot are retreating from whatever disaster has befallen, fighting to survive. The campaign can be about what comes immediately after, how to rebuild, forge new alliances, establish new bases and setup defenses against an occupying force, shaping the new direction the world will take, etc.
If the setting is more about what type of world emerges after the fall, then maybe setting the timeline a decade or two after the fall might be best. That way the old world is recent enough to remain relevant and in people's memories, but old enough that the new order has already begun to set in place and new players (in terms of dominant factions, societies and such) have begun to emerge and establish themselves.
I think making it too long after the fall makes it kind of irrelevant or just ancient history (which might add flavor and depth, but doesn't have much to do with the PC's current circumstances), unless we're talking Post-Apoc level cataclysmic falls.