It probably doesn't matter very much, but you should most likely use the current name of the city where you were born. There's no harm in giving both the current name and the name it had when you were born.
The instructions pay more attention to the country than to the city because of the rules that determine your "foreign state of chargeability." The Foreign Affairs Manual states the rule at 9 FAM 503.2-2(1):
Changes in territorial limits: If an alien’s place of birth has undergone changes in political jurisdiction since the time of his or her birth, the alien is subject to the foreign state limitation of the state which has jurisdiction over that place of birth at the time of visa application.
The most important thing is for the information you give to identify the current state that contains the place where you were born.
Mike Harris suggested in a comment that you should list both, and that seems sensible if the form has enough space. You might even make it less confusing for anyone who is unfamiliar with the name change by adding "then called", for example Podgorica (then called Titograd).