I know many Jews whose actual bris-given name is Alexander, and this has been a popular name even among great tzaddikim of the past (such as R. Alexander Ziskind). I've heard a legend (mentioned on sites such as Ohr Somayach, Aish, and JewishHistory.org) that when Alexander met with the Jews and supported them(Yoma 69a), the Jews in turn honored him by naming children 'Alexander'.
(See also Igros Moshe O.C. 5:10 where he rejects another version of the story)
What's the earliest source for this story/explanation?