http://en.wikipedia.org/wiki/Dhul-Qarnayn#Alexander_the_GreatIt is most definitely a legendary reference to Alexander the Great.
The "Two Horned" reference comes from the fact that Alexander was deemed a god-man by the priests of
Amun-Ra and that symbol of divinity were the two-horns. The ancient coin below is a representation of Alexander as a god with the two horns.

This usage of the "two horned one" in reference to Alexander was quite prevalent in the ancient mideast and was carried eventually into the Christian era (ie Christian Egypt, Syria, Palestine). During the early christian era the Christians began revisionist process of recasting old classical pagan figures as righteous monotheistic ones. This is the beginnings of the
Alexander Romance. These mythical and false representations of Alexander as a sort of righteous believing David/Solomon-like figure was absorbed into many ancient mideastern christian cultures at the time.
These myths naturally travelled into Arabia too and so when Prophet was a merchant it is highly likely he learnt of the mythical stories of Alexander and Muhammad most likely took it as historical fact - being a simple arab merchant without any divine knowledge. And, as expected, that mythical representation of Alexander was also reproduced in the Quran along with all its erroneous implications. Most Muslim scholars considered Dhul-Qarnayn to be Alexander, though some smarter medieval scholars who actually read history realized the
real Alexander was actually a pagan bisexual warmonger and tried to shoot down the Alexander identification.
Only in modern times are mainstream muslims denying that Dhul-Qarnayn is Alexander because it is now common knowledge that Alexander was nothing like what the Quran describes.