Other ‘new cities’ (the answer)
But the answer I had in mind is both more ancient and more historically significant than those cities: Carthage. It is known in Latin as Carthago or Karthago, in Greek as Καρχηδών or Karkhēdōn, and in Arabic as Qarṭāj. Its Phoenician name was Qart-ḥadašt meaning ‘new city’ which acknowledged its relationship to Tyre, from which many of the original Carthaginians came. (The second part of the name is cognate with the Modern Hebrew ḥadaš ‘new’; Semitic languages typically feature the noun-adjective order, which is also typical of Romance languages).
Curiously, Cartagena in the Spanish region of Murcia was founded around 227 BCE also as Qart Hadasht by the Phoenicians. The city’s heyday was during the Roman Empire, when it was known as Carthago Nova, or the New Carthage (the city’s other name was Carthago Spartaria). Thus, in essence it was called ‘the new, new city’.