I didn't see the interview so I can't offer any type of informed commentary on it.
I don't watch Letterman anymore because I never found him to be particularly funny. He's something of a one-trick pony....if you've seen him perform once, that's pretty much it.
The question that O'Reilly pitched to him is the type that a real debater or statesman such as Churchill, Roosevelt, Reagan, or even Clinton would have smacked over the fence. Letterman shouldn't have had that much trouble in answering it.