The episode
Aquiel (TNG, sixth season) established that as little as within a decade or so before the events of TNG, there were still skirmishes between Klingons and Starfleet.
This is even in the 'peaceful' version of the 24th century.
Even in the TNG/DS9 era, it's an uneasy alliance...
not an easy thing for either side... in
Heart Of Glory Riker and his away team react with suspicion of the three Klingons, while later Klingon stories would see the Empire being openly scathing of humans (Gowron virtually dismisses Picard's legitimacy as Arbiter Of Succession, until he figures out a way he can make it an advantage of course

).
So, the potential for conflict was always there... even
after the so-called "peace accords" established in
Star Trek VI: The Undiscovered Country.
My suspicion is that in the
Yesterday's Enterprise universe, the gradual mothballing of the fleet after the Khitomer accords resulted in Starfleet being unprepared for a Klingon assault. The Federation was left impotent after the events of
STVI. Klingon ships are more seat-of-your-pants in their construction anyway, so even if the Klingons had to similarly "disarm" after
STVI, they could probably have built up a credible fleet again much faster than Starfleet. Chances are good that by the time the alternative Federation actually realized they were at war with the Klingons again, and scrambled to put ships into action, they had been (metaphorically) caught with their pants down, and struggled to play catch up. No doubt there was a while where diplomatic solutions were sought as well, which probably gave the Klingons even more chances to stockpile a battle fleet on the sly.
In short: the Starfleet didn't know what him 'em.
