No more foul-smelling barbarians!
It would be nice to go back to a more TOS approach to the Klingons - they can be pretty darn bad, but they also can have an air of refinement or sophistication to them. I mean, look at Koloth in "The Trouble with Tribbles". That characterization as presented there is hardly like what you would expect from a cardboard cut-out TNG-era Klingon. I believe a fan once asked William Campbell if he could speak some Klingon. He replied with something along the lines of "Why sure... 'My dear Captain Kirk!'"
I know the big three TOS Klingons were brought back in DS9 "Blood Oath", but it seemed like they tried to transform them into TNG Klingons (and I'm not just talking about the makeup.) I think they did a lot better with Arne Darvin in "Trials and Tribble-ations", however.
Granted, TNG and DS9 developed Klingons a lot more than TOS - but then again, TOS was only three seasons and didn't have a main character who was Klingon. However, you could start with the premise of the less-barbaric TOS Klingons and simply develop them in a different direction. It is an alternate timeline, after all...
Regarding the whole Cold War issue - it was a very interesting dynamic, but why do it again? Besides, it's the 21st century - maybe they should explore an adversarial relationship that's more relevant to today.
Basically, I wouldn't want them to do Klingons at all if they just do what's been done for the past twenty years - it's been done to death. Mix it up, please. There will never be a better opportunity.