When did the name change happen, was it something that happened immediately or did people have time to prepare? Who wanted the name changed? was their strong opposition? Were there any other names possible for the city? Finally on a semi-unrelated note, were there any other famous cities that suddenly changed names. (New York/New amsterdam).
As you most likely know, the city of Constantinople served as the capital of the Roman Empire from 330 AD onwards, and after the two halves of the Empire [East and West] were divided administratively between Theodosius I's two sons in 395 it served as the capital of the Eastern Roman Empire (later known as the Byzantine Empire).
As a city Constantinople had been settled by Megaran [Greek] colonists circa 667 BC, and was originally known as the City of Byzantium (which legend tells is named for the settler who founded it, Byzas). This historic name for Constantinople is where the name Byzantium [referring to the Empire] was derived from much later during the medieval era.
The city was renamed Constantinople in honour of Emperor Constantine I, who did much to grow the city until his death in 337 AD. Despite several other names in common usage prior (for example the designation 'New Rome' was popular), Constantinople remained the most popular name for the city well beyond the eventual fall of the Byzantine Empire to the Ottomans and into the early 20th century.
By the time of the Fall of Constantinople in 1453, the Byzantine Empire had lost the vast majority of it's territories both in Asia Minor and the Greek region, as well as the influence and power it once had. Indeed, several European powers diverted the Fourth Crusade towards Constantinople and sacked and partially destroyed the city, highlighting the weakness of the Empire in it's dying years. Indeed the city had later been the seat of the Latin [Romanian] Empire after it was conquered from the Byzantines, until Emperor Michael VIII Palaiologos and his generals recaptured the city of Constantinople from the Latin Empire in 1261 AD.
At this point Byzantine rule was confined to the city of Constantinople, it's immediate surroundings and the Greek island of Achaea, and when the flourishing Ottoman Empire sieged and conquered the city in 1453 [an event known as the Fall of Constantinople], the Byzantines were clearly far too weak by this point to ever again reconquer the city.
So by this point it's quite clear that the name Constantinople was steeped in Roman history - but after the Ottoman conquest the name was not immediately changed. Indeed, for many years after Sultan Mehmed II took the city Constantinople was still it's 'official' name - the official Arabic name at the time, Kostantiniyye, is a calqued translation of the this.
Even before the Ottoman conquest however the name Istanbul was a common informal designator for the city amongst the Turkish peoples, deriving directly from the Greek phrase "στην Πόλη" "to the City" - a common informal name for Constantinople amongst Greeks of the period was to simply refer to it as "The City". However this name was by no means official and the Turkish translation "Kostantiniyye" was still used in all official circumstances. So at this point Istanbul essentially served as the "people's name" amongst the Turk populace, whilst all official sources kept the direct connection to "Constantinople". This name was kept officially into the 17th century, and for a brief period in the 19th century.
It's important to note after the conquest the vast majority [about 30,000] of Byzantine citizens in the city were deported, so at this point whilst there were Greeks in the city it was now very much a Turkish place both culturally and territorially. Up until the formation of the Republic of Turkey in 1923, Istanbul remained a popular alternative name for the city, becoming part of the official language and used semi-officially and officially in later times, serving a period of interchangeability between the use of "Kostantiniyye" and "Istanbul".
When the Republic of Turkey was founded in 1923, the term "Kostantiniyye" was aggressively disassociated with the language by the government, with requests made by the government to foreigners to cease the use of the name Constantinople with the Postal Service Law of 1930, and letters or items addressed to Constantinople sent via postal service to Turkey were no longer delivered. This resulted in a rapid decline in use of the name "Constantinople", and the adoption of "Istanbul" both officially and unofficially.
Further alternative names? Stamboul was used from the Middle Ages onwards as a sort of 'Westernisation' of the term Istanbul - although referring to the city as Constantinople was still by far the predominating method in the West until the formation of the Republic. Islambol was another semi-official name coined after the Ottoman capture of the city and used by Turkish peoples - if I recall it refers to the newly-conquered city as the heart of the Ottoman Empire and Islam.
One other famous city that had several sudden name changes was St.Petersburg, which in 1914 was Russified to Petrograd at the outbreak of WW1. In 1924, when Lenin died, the city name was changed to Leningrad. After the fall of the Soviet Union in 1991, it was changed back to St.Petersburg. Source: http://en.wikipedia.org/wiki/Saint_Petersburg
The city of Medina was called Yathrib before the Prophet Muhammed renamed it to Al-Madinah Al-Munawwarah ("the radiant city"). Al-Madinah/Medina alone is the short form and just means "the city". Source: http://en.wikipedia.org/wiki/Medina