So if a time-traveling mischief maker gave the NSA a copy of "The Klingon Hamlet" in 1980, would they have been able to "decrypt" it?

That's a difficult case. It would depend on the resources thrown into it. If it were formatted as a play it wouldn't take long for someone to notice that, and the five acts would to an English speaker suggest Shakespeare. (This isn't a hypothesis someone would immediately hit upon but it is the sort of thing that someone would eventually think of.) At that point things will be much easier since we have an effective Rosetta stone. However, note that even with the Rosetta stone, the deciphering of Egyptian hieroglyphs took a very long time even after the main breakthroughs.

If the text were not the text of Hamlet but were a similar random text of the same length, then it is almost certainly not long enough to be decipherable in any reasonable span of time. I don't however have any idea how much longer the text would need to be.