It's clear to me what's going on here. What we're seeing are multiple timeline incursions from the Temporal Cold War.
At some point in the future, one of the factions decided that it can alter history for their betterment if Spot died. So, at some undisclosed time, Future Guy managed to get some Suliban into the twenty-fourth century. They boarded the Enterprise without being detected and killed poor Spot. This in turn sent massive shockwaves throughout history.
Temporal Agents from the thirtieth-century realized that without Spot there would eventually rise a Dominion-Borg Alliance which would crush all Alpha Quadrant species. So, they enlisted Seven of Nine to time-travel back in time to stop the Suliban.
Seven was unable to save Spot. In fact, she made the situation much, much worse when she assimiliated the entire Enterprise crew. The Temporal Agents soon realized they made a mistake in using "Season Four Seven" instead of "Season Seven Seven." So, they enlisted someone else to fix the timeline.
This time they turned to Garak. Now, a simple tailor wouldn't make for a good Temporal Cold War Operative. However, as we all know, Mr. Garak is no simple tailor. He was sent back in time to stop the Suliban from boarding the Enterprise and to stop Seven of Nine from assimiliating the entire ship. The only problem was that something went horribly wrong in the time matrix threshold, and Garak's natural Cardassian paranoia took control of his mind. Once on the Enterprise, he reconfigured the weapons systems to attack the Gorn Homeworld, which they happened to be orbiting at the time. This led to further timeline shockwaves, which allowed the Dominion-Borg Alliance to crush the Alpha Quadrant more easily.
Finally, the Temporal Agents realized that if they let this go on much longer, Spock would eventually be poisoned, which would cause the complete destruction of the multiverse. So, they travelled back in time personally to stop the Suliban. They also were unable to save poor Spot's life. However, they brought along a back-up plan, another cat. This cat happened to be female, whereas the original Spot was male. Thankfully, nobody ever noticed when they switched the new female Spot for the dead male one.
And so, the Alpha Quadrant was saved.
And now we all know why Spot changed genders.
The Trek Encyclopedia notes that in addition to the occasional gender gaffes, the actual cat species changed in different episodes. They're naturally very similar looking species, but not identical.
