Klingon intentionally has a weird phonology. Not in the actual sounds that are used, which are normal human language sounds, but rather the pattern of sounds: it has several prominent holes in its phonology.
For example, Klingon has the velar nasal /ŋ/ and velar fricatives /x/ and /ɣ/ (which sound like sounds from French and German), but it does not have the velar stop /k/. Meanwhile, it has the uvular stop /qʰ/ and uvular affricate /qχ/, but no other uvular sounds. It would be very likely, in a natural language, if this kind of weird gap arose, for either the two series to converge on one point of articulation (for example, shifting /q/ to /k/ and /qχ/ to /kx/), or alternatively for new consonants to spring up to fill out the phonology at each point of articulation (for example adding /k/ and /χ/ as phonemes).
And while Klingon has the affricate /tɬ/ and the affricate /tʃ/, but the only alveolar or postalveolar fricative is the retroflex /ʂ/, which seems like it would merge with either /ɬ/ or /ʃ/.
Similarly, while Klingon contrast the voiceless stop /p/ with the voiced stop /b/, it contrasts the voiceless stop /t/ not with the voiced stop /d/, but rather with the voiced retroflex stop /ɖ/. It's pretty weird, to articulate it as retroflex rather than plain voiced, and it seems likely that Klingon would undergo a sound change: first the retroflex consonant would be in variation with the plain stop /d/, and then it would be dropped in favor of /d/. Of course, any description of a language is just a snapshot of it in time, with changes behind it and changes to come.
Now in practice, these uvular consonants are very difficult consonants for native English speakers to produce, and I think that a great deal of spoken Klingon has speakers using /k/ instead of /q/, or /d/ instead of the retroflex /ɖ/. Marc Okrand seemingly addressed this somewhat in The Klingon Dictionary:
There are a number of dialects of Klingon. Only one of the dialects, that of the current Klingon emperor, is represented in this dictionary. When a Klingon emperor is replaced, for whatever reason, it has historically been the case that the next emperor speaks a different dialect. As a result, the new emperor's dialect becomes the official dialect. Those Klingons who do not speak the official dialect are considered either stupid or subversive, and are usually forced to undertake tasks that speakers of the official standard find distasteful. Most Klingons try to be fluent in several dialects.
Some dialects differ only slightly from the dialect of this dictionary. Differences tend to be in vocabulary (the word for forehead, for example, is different in almost every dialect) and in the pronunciation of a few sounds. On the other hand, some dialects differ significantly from the current official dialect, so much so that speakers of these dialects have a great deal of difficulty communicating with current Klingon officialdom. The student of Klingon is warned to check into the political situation in the Klingon Empire before trying to talk.There does seem to be a great deal of continuity in spoken Klingon between different eras (as much as in the English of these periods), although some of this might result from the prominence of Colonel Worf (an official of the Klingon Empire who defended Captain Kirk in court) and Lieutenant Worf (a later officer of the USS Enterprise). Interestingly, according to Okrand, English has a position of high prestige in the Klingon Empire, serving as a signal of elite status and a private means of communication among starship officers. If Klingons use English as a signal of social prestige, it doesn't seem implausible that, in Klingon, they would use a somewhat artificial, archaic, and difficult-to-pronounce sociolect as a prestige dialect as well.
Dialect can explain some of the problems with voice acting in Klingon. But it's just too difficult for Anglophones to pronounce. Christopher Plummer's General Chang in "Star Trek VI" is a great character, quoting Shakespeare even more than Kirk does in some of the earlier movies. Except when he's speaking Klingon: the only time he does it, at Kirk's trial, it is a bunch of disconnected syllables that don't display the interesting morphology of the language.
Mark Okrand talks about the creation of the Klingon language in this series of videos (1, 2, 3, 4, 5). Since the Klingon language was created on the set of "Star Trek III", Okrand was able to incorporate the actors' performance errors into the canonical version of the Klingon language. "My sort of 'role model' of what Klingon sounds like is Christopher Lloyd saying it, because he was my first big speaker," Okrand says.
However, Michael Dorn, who played Worf on "Star Trek: The Next Generation" and "Deep Space Nine", as well as three of the movies, has probably spoken more lines of Klingon than any other actor. He's also done a lot of voice work narrating audiobooks on the languageand videogames (such as Star Trek: Klingon), although in the audiobook of Conversational Klingon, Okrand pronounces all the Klingon words and phrases. Dorn is also kind of awesome.