There have been a lot of explanations offered as to why and how All-Star Superman's benevolent super-genius, Leo Quintum, could also be its evil super-genius, Lex Luthor. I thought I'd collect and categorize the best clues right here - and, in doing so, I think I've inadvertantly compiled a pretty good argument as to why this series is so incredibly awesome.
The Morrisonian: Grant Morrison absolutely loves two things: drug-induced epiphanies and time-travel. Luthor experiences the former when he ingests the vial that gives him Superman's powers, and it's no small stretch to imagine that he could have subsequently traveled to the past in order to do something about his new perspective, thus fulfilling the latter.
The Superficial: They wear very similar coats. They like to clasp their hands behind their back. Leo looks young, but uses a cane, which would seem to imply that he's possibly older than appearances suggest - or it functions to change his posture and disguise his body language. (The age issue is also tricky, of course, since Lex's reason for trying to kill Superman in issue 1 had a lot to do with Lex getting old. So maybe Leo looks younger because a redeemed Lex has actually reversed the aging process?) Quintum has hair and glasses, but this also makes sense as a disguise: hair and glasses are what differentiates Clark from Superman, after all.
The Merely Suggestive: In Quintum's very first appearance, he throws out a comment that is never revisited but seems mighty suspicious: "I'm trying to escape from a doomed world too, Superman... It's called the past." And when Superman gives Quintum his DNA later in the series so that he can build new Supermen when Clark dies, Quintum's reluctance is similarly provocative, as he tells Superman that "I could be the devil himself for all you know." Since Quintum doesn't eventually betray Superman, this exchange serves no purpose unless Quintum in fact is the nearest thing that the DC Universe has to the devil, albeit a reformed devil.
The Suggestive as Supplemented by the Pseudo-Scientific: Superman's response to Quintum's comment about being the devil is, just as interestingly, "Oh, I think I'm a better judge of character than that, Professor. This is how much I trust you, Leo." We could take Superman at his word, that he can separate the good apples from the bad, but recall that Superman had just used his x-ray vision to write out his own DNA sequence. The dude can read DNA strands. Again, if this exchange is simply an admission of trust in a character that we had never met before this series and have been given no reason to distrust, then it's not a particularly moving or necessary scene; but if Superman has read Leo's DNA and knows that he's Lex, it's a staggering and moving display of confidence in his former nemesis.
The Textual: Leo's line about maybe being the devil is additionally ironic because Lex, especially in this series, has often been compared to the Miltonic Satan. A self-deluded narcissist who squanders his considerable powers in petty efforts to prove himself superior to Superman, Lex - to quote Superman in A-SS #12 - "could have saved the world years ago if it really mattered to [him]". But like Milton's Satan, Lex is more interested in power and proving himself deserving of power than he is with saving the world - he'll even risk the world's safety by killing Superman in pursuit of his self-actualization. Additionally, Leo's last name has a more direct connection to Milton's Satan, as Macon Cheek has suggested that Milton actually produced a literary precursor to his Paradise Lost Satan in an earlier poem. And the poem was titled "In Quintum Novembris."
The Numbers: For those who look for clues in seemingly conspiratorial patterns of numbers, there's a lot here to play with. "Quintum", in addition to having a certain phonic relation to "quantum" - and quantum mechanics are related to time travel, to tie this back to an older point - quite obviously has the latin number five imbedded in it. But where else do we see that number? Well, Lex's focus issue is #5, his prison jumpsuit is 221 (2+2+1=5), and at his trial he's situated as the fifth truly evil personality in a line that includes Adolf Hitler and Genghis Khan.
The Thematic: Thoroughout the series, Superman is resolute in his belief that humanity is capable of doing everything that he has done, that they will be no worse off without him if only they believe in themselves. Though he tells Lois that he's the only person strong enough to lift the key that opens the door to the Fortress of Solitude, he also hopes that "One day some future man or woman will open that door, with that key." His fortress, he explains, isn't a "museum", but rather a "time capsule" - not a record of some past age of superheroes but an example for the one that is yet to come. And this lesson is all the more meaingful if Lex Luthor himself, as Leo, is seemingly on the verge of creating the new man or woman who will be capable of lifting that key. Further to that point, Cole Moore Odell suggests that when Superman admonishes Lex in the final issue for wasting his genius we should read it as a challenge rather than a rebuke - a request that Lex, having seen the error of his ways with Superman's super-senses, will refocus his efforts and actually save a world without Superman. And he'll even do it in the way that Superman suggested: "years ago." His reformation, then, is Superman's greatest triumph - a moral victory that manages to touch even the most cynical and skeptical of us. (Which is to say: it reforms the Lex Luthor in all of us.)
The Silly: So we've touched on nearly everything right? Except for why he named himself "Leo". It's similar to "Lex", sure, and it could simply be that Morrison wanted to drive home the fact that they're mirror-reflections by opposing Lex's "X" to Leo's "O". (Get it?) But there's somethign else - Leo Quintum isn't the only Leo in this series. In a blink-and-you-missed-it moment in issue 5, Lex briefly introduces his Superman-costumed primate to Clark Kent. Its name? Leopold. It's a connection that's at once hilarious and convincingly self-effacing: if Leo is Lex, then Lex has genuinely swallowed his pride in naming himself after a monkey. No wonder Superman felt he could trust him.