The fact that this very same debate, or with slight modifications, is found all over the internet but with different protagonists (e.g. atheist professor, Muslim student http://www.myiwc.com/forums/archive/index.php/t-3067.html) should be strong evidence that this is a myth.
If you do a quick google search on "Atheist Professor", you will get countless variations of the same theme: Smug, arrogant atheist professor is humiliated by Einstein/Evangelical Christian/Muslim scholar.
The Einstein version was debunked by Snopes:
Although 2004 tellings of the legend name Albert Einstein as the faith-driven student, there is no reason to suppose the renowned physicist had anything to do with the fictive incident. Biographies of the man are silent on his having dealt one of his teachers such a comeuppance. Moreover, this famous scientist gets used in legends whose plots call for a smart person, one whom the audience will immediately recognize as such (i.e., modern tellings of an ancient legend about a learned rabbi who switches places with his servant feature Albert Einstein in the role of esteemed scholar). This venerated cultural icon has, at least in the world of contemporary lore, become a stock character to be tossed into the fray wherever the script calls for a genius. (Thankfully, contemporary lore has other uses for him too. In a legend of entirely different character, Albert Einstein was rumored to have made a guest appearance on the television western Gunsmoke.)
EDIT: Doing a Google search for each year since 1990 individually, the first hit I got was in 1997. It tells the story, but does not name Einstein: "Things on Which to Reflect"
This, of course, still does not prove that the story is wrong, but, if Einstein genuinely said this, there should be an earlier reference, given that he died in 1955. Add to this that the only sites that mention this have a clear religious intention and do not cite a source for their claim. I believe this is more than sufficient to demand evidence from the other side, and, lacking this, refusing to believe that Einstein really said this.