My theory is that the Klingons were seperated into several social castes, and the "smooth-heads" had dominion during the first years of Kirk's voyage. The "ridge-heads" were the hunter/warrior caste that you just don't see in the old episodes. Sometime between the classic episodes and the first motion picture, possibly started by the tribble famine, the warrior caste overthrew and wiped out the "flat-heads" (perhaps a royal line?). Since the remaining species had a much more punctuated ridged head, future generations developed more prominent ridges.
I think this theory can be backed up by the fact that much of Klingon technology couldn't have been developed by such a brutal species, so at some point in their lineage there had to be scientists and a government that cared enough to progress technologically.