From what I understand of the Klings, I'd think that after humanity suffered such a huge and embarrassing loss, they would ally with the Romulans. Wouldn't Klingons would see that as a failure? Either the Humans couldn't develop technology fast enough to prevent such an event, whether by detection of cloaks, or some type of advanced shielding. What I also know of their character would suggest that they would see that as a weakness. But, can someone perhaps correct my vision?
You probably should have linked to the Tomed Incident, since it's not a very well-known event, even among Star Trek fans. With that said, the Klingons and the Romulans had a long and storied history, including a period of alliance, followed by a violent falling-out. This culminated in the Khitomer Massacre.
From a geopolitical standpoint, the Klingon-Romulan Alliance seen in the final series of TOS - though the series was cancelled before the alliance was openly acknowledged, the plan was definitely to have the two powers officially ally against the Federation - was aimed at the growing threat of the Federation. If the Klingons and Romulans were attempting to utilise traditional "balance-of-power" (for the record, I have a background in international politics, and I think BoP is a crock in both theory and practice, but that doesn't diminish its popularity) politics against a common foe, it would make perfect sense for the Klingons to switch sides if the Federation became too weak and it appeared that Romulus was the greater threat. This is a very similar argument, after all, to the one Benjamin Sisko and Jadzia Dax have regarding the Romulan treaty with the Dominion during the DS9 classic In the Pale Moonlight. Even the Federation Alliance which resulted from the events of that episode was an uncomfortable one, especially where the Klingons and Romulans were concerned, and that was with the threat of the Dominion as a catalyst.
Even though the Tomed Incident took place before the Khitomer Massacre, it took place after the Khitomer Accords and possibly (this is uncertain from the films and television programs) after the signing of the Treaty of Alliance between the Federation and the Klingons. It would have required an incredible volte-face on the part of the Klingons to turn on their Federation allies to side with the despicable Romulans just because of a major setback to the former. It would also have been very dishonourable, and the Klingons place a very high stock on honour, even though most Klingon politicians seem pragmatic enough to set honour aside when necessary for the Empire.
James' answer is a good primer on the political side of things, but perhaps even more important is the cultural aspect. The Klingon culture ideally places much higher emphasis on honor than they do victory. In fact, a recurring theme throughout DS9 and The Dominion War is that the culture was shifting towards a policy of victory before honor - something that ultimately started swinging back the other way when Martok took office as Chancellor. Humans, while initially threatening from a political standpoint, ultimately proved to be fairly honorable - both as opponents AND allies - whereas the Romulans (who embrace a "win at all costs, especially through guile & deceit if possible" attitude) proved to be less than reliable during the brief Klingon-Romulan alliance.
Even following years of war between the two, the Federation offered the Klingons assistance when Praxis - the primary energy production facility of the Klingon Empire - was destroyed. This compassion confounded the Klingons, but eventually they came to accept the humans as allies. Had the Romulans offered the aid instead of the Federation, it's entirely possible that things would have turned out differently... but compassion is not in a Romulan's nature. Reinforcing that aspect of the Federation later was the Enterprise-C's destruction while attempting to save a Klingon colony from a Romulan attack.