The real problem with this style of interview question is that it is good for those who talk well, and bad for those who don't talk well. I have seen my fair share of candidates who are great talkers, but can't code for crap. The interviewers who didn't ask coding questions loved them, but those of us who made them code knew they sucked.

You should have stuck with programming on the white board. That's the right way to find good programmers.