Here is an incomplete list of streets in Jerusalem that have been renamed at some point (mostly in 1948), followed by their original names.
I was planning on adding this to Wikipedia, but I don't see a good place for it.
Keren Hayesod - King George 
King David - Julian's Way 
King Solomon - St. Louis Way 
Shlomtzion - Princess Mary Ave 
Straus - Chancellor 
Agron - Mamilla Road 
Shivtei Yisrael - St Paul's Road 
Malchei Yisrael - Geula Road 
Herzog - Gaza Road 
Usishkin - Yehudah Halevi 
KK"L - Shmuel Hanagid 
 Collins & LaPierre, O Jerusalem, 1972