How many USN personnel spoke Russian during the Cold War?
During the Cold War? Probably a few aboard every major ship.
If the Federation/Starfleet had enough information on the Klingons to compile translation dictionaries, there should have been personnel aboard the Enterprise who spoke the language. They departed Earth on a diplomatic mission that would meet the Klingons, inspite of the presence of the UT, there should have been a Klingon cultural expert on board who spoke the main Klingon language.
And as others have noted, if there were no one aboard who spoke Klingon, the UT could have give a display of the incoming transmission from the Klingons, and provided (again a display) the proper response, plus a correct pronunciation in Uhura little blue-tooth.