On the one hand, I laughed out loud and said to my wife, "What, she expected the Federation to still be around after all that time? Good luck with that!" during that scene.
Some of the individual Imperial Dynasties of China ran over 500 years, and collectively, Dynastic China lasted from 2070 BC to 1912 AD - over 3900 years! Rome was founded in the 8th Century BC, and the last Roman Emperor died in 1453, over a thousand years run there. Yes, those things experienced massive changes over time, but they were, in some real senses, still continuous things.
So, long-lasting cultural lineages are not all that far-fetched. They are, instead, the foundation of much of what we currently call our civilization.
And, "The Federation" is not a "nation" in our normal sense of the term.
Honestly, if I was her, I'd be hoping that something better than the Federation existed by then. Not the Federation itself.
Starfleet officers are frequently types who strive for continuous improvement in themselves, their organization, and their government. You can have something that was better than the Federation she knew, that is still "the Federation" in name and a sense of lineage and base principles, even if elements of the implementation has changed.
It is a bit... overly-convenient to the criticism to take it she meant EXACTLY the same thing she remembered would still be there. She's a highly-educated officer. She knows history. Don't assume she's a fool.