Kirk: "They've invaded our territory, killed our citizens."
Did we ever SEE any of that, though? Even the Romulans were SHOWN to do some damage in their first appearance.
But what did we "SEE" the Romulans do? Set a single room on fire in a outpost and likely kill the one person located there. Later they kill one more person aboard the Enterprise after it is attacked. That's all we are shown. We know through dialog that a number of outposts were attacked and destroyed, their personnel also "destroyed."
It is the same with the Klingons, we know through dialog of their deeds, they were capable of invading the Federation and killing people there. They're powerful enough to issued a ultimatum to the Federation without being simply dismissed.