The question isn't really about whether navies (modern or futuristic) have alternative uniforms, though. It's about the [in]consistency of the presented universe. If the Enterprise crew wearing the DS9 uniforms had been phased in during the last couple seasons of the tv show, all these threads that question the mismatched look in "Generations" wouldn't keep coming up on here every few months. People would just accept it better. Instead, it does tend to raise questions, even though the answers are actually very straight-forward.
I doubt I'll ever live to see a day where people stop asking Trek questions for which straight-forward answers are readily available...
I think the jumpsuit was new and came with everything new Starfleet did. When DS9 became a starfleet commanded post it was something new. DS9 also got runabouts. When the Enterprise D received her refit between the show and Generations she also got some new jumpsuits too. Voyager got the new jumpsuits too instead of the TNG style that other operating starships still used. This was the idea until drastic fashion changes resulted in overhauling the system altogether and making nice dark uniforms that everyone would change too as they were more in tune with combat...
We got to see the uniform switch take place on DS9 when they went to the First Contact-style uniforms mid-season. In fact, you can see the two uniforms side-by-side in DS9: In Purgatory's Shadow, when they find the real Bashir on the Jem'Hadar internment camp. He's still wearing the DS9 style uniform, implying that he was kidnapped before everyone else on DS9 switched over to the new jackets. Me personally, I had zero problems with the Generations uniforms switcheroo. As others stated, modern militaries have multiple approved uniforms. Just because we never saw them wear the jumpsuits on TNG doesn't mean that wasn't an option available for them.