Here is an audio sample of the Klingon language from the previously linked video of the Klingon computer game.
It is a very quick first draft. I've managed to remove a fair amount of the background engine noise without affecting the speech. The air between phrases can be muted and the use of equiliser and reverb to give the speech more of a rumble can be tweaked to perfection.
It shows that within this sample, there is plenty of material to construct viable, crisp and distinct dialogue. Considering the gutteral, confident tones, this could very well be the commanding officer's voice.