Names of people and places have always been perceived in the conscience of Russians as something necessary, permanent. A Russian proverb says: “С именем – Иван, без имени – болван” (With a name he is Ivan, without a name he is nobody.) Another one goes: “Корова без клички – мясо” (A cow without a nickname is a piece of meat.)
When forced to change a name it is seen as a real disaster. Личное имя (personal name), название поселения (the name of a place), народности (of your origins) are all symbols of the spiritual side of a man's life. In Russia, the name of your home place is always treated with respect and love. Therefore before the October Revolution, it was extremely rare to rename a street, a village or a town.
In 1658, Tsar Alexis of Russia ordered to specify by writing that Чертольем (Chertolem) will become “улица Пречистенка” (Prechistensky Street). Since ancient times, close to the actual subway station “Остоженка” (Ostozhenka), there was a deep ravine nicknamed “Черторый” (Chertory) or as would called the people “чёрт рыл” (dug by the devil). And so, the entire district was called “Чертольем” (Chertolem), and this is how the street got its name.
По Большой Чертольской улице проходила дорога в Новодевичий монастырь (the Bolshoi Chertolskaya Street led to Novodevichy Convent), and its main church “Пречистенский” (Prechistensky, in honor of the Blessed Virgin Mary.) Noticing the incompatibility between the name of the street and the way it was leading to, the Tsar ordered it to be renamed. Muscovites understood the reason of such a idea and the name was changed, and since then is called “Пречистенка” (Prechistenka).
But the renaming of the Arbat Street of Smolensk was rejected by Muscovites, though the reasons brought by the Tsar were similar (the street led to the Church of the Icon of the Mother of God of Smolensk.) It might be that the name of Arbat doesn't have any negative connotations.