Is it really credible that the Federation would be fighting a losing war with the Klingons after twenty years? Why were the Klingons winning? What happened to the Romulans? Why would a Romulan attack on a Klingon colony cause a war between the Klingons and the Federation in the first place?
The easiest to answer of those questions would be the last one, which had an entire episode to answer it. "TNG: Yesterday's Enterprise" main plot was that it wasn't about the Romulan attack on Narenda III causing a Federation-Klingon war. It was about the act of the Federation sacrifice to defend the Klingons had the diplomatic power to prevent a later Federation-Klingon war. The reoccurring theme throughout the Original Series and the first six movies was the threat of the Klingons. In the briefing room scene at the beginning of Star Trek VI, Spock references that there was "seventy years of unremitting hostility with the Klingons". These two powers were on the brink of war for nearly a century. In the Yesterday's Enterprise's (YE) timeline, it's not hard to believe that just another decade or two of tension finally erupted somewhere into total war.
The movies also prove the example of the threat that Klingon ships posed. In Star Trek VI, although the Klingons had a huge (initial) advantage of a battle cloak, a single Bird of Prey was able to inflict significant damage against a Constitution and Excelsior class starship. Considering that the D7 Cruiser was the Klingon's real ship of the line, the Klingon fleet was definitely a match for Federation Forces. Again, it's not that much of a stretch in the YE timeline for one or two critical engagements to go poorly for the Federation, and start a slide towards eventual defeat.
As for the Romulans, it's has also been a recurring theme of Star Trek that all three powers are not fond of each other. The Klingons and Romulans were definitely not fond of one another. So why would they enter a war where two of their enemies were weakening each other and save one of their rivals?
The hardest question to answer is the first one. There was no reference as to how the Federation came to be doing so poorly in the war. The best that can be accomplished is pure speculation. However, twenty years of warfare can grind any economy to dust. Considering how much of a threat the Klingon ships posed tactically, and how the Klingons could fare better in an extended war with their warrior culture, all it would take would be a Battle of Midway type battle that would begin putting the Klingons at an advantage. Regardless, it was an alternate timeline, and a pretty badass one at that.