A combination of dramatic necessity and writing/production is why the battles themselves seem kind of weird.
Trek's hand-to-hand is always terrible. Kira getting stabbed and then taking her attacker out provides an excellent visual of the kind of fight choreography that permeates the franchise. So she gets stabbed, but manages to react, yank the blade out, smack the arm that holds it forcing it to drop, and then pummel the guy who was holding it. Right there is the problem: the moment
she yanked the knife out, any halfway competant fighter would have attacked her again instantly (in that moment, an elbow to the head would seem to be a good choice). But instead, the Klingon just stands there, letting her attack. It's like a turn-based RPG: he used up his turn trying to stab her, so now he has to wait. Ohh, she got a critical, so he's KOd! Tough luck.
Trek combat is always like this. Similarly, the space battles - while they to LOOK cool - have very little logic to them (especially when you consider the "range of weapons as stated by dialog vs. as shown by visuals" problem). In my mind, there's no good way to resolve these issues with an all-encompassing, in-universe explanation that doesn't end up boiling down to the entire galaxy being populated by idiots.
But, brushing the out-of-universe inconsistencies aside, to offer a different take on the OP's main question: it wasn't that the Klingons were weaker than they should be, or that the "warrior race" thing is a bunch of hoopla. Rather, the reason they were losing is because the likes of Starfleet and Bajoran military officers are BETTER than the Klingons had thought.
We didn't over
estimate the Klingons' fighting prowess, the Klingons under
estimated their opponent's fighting prowess.