One reason for the paradox could be that solving a problem on a whiteboard or in a similar interview situation is different from actually writing a program. I could easily see myself failing the fizzbuzz test on a whiteboard. My programming style is highly iterative, even on a micro-level. I don't expect what I write down in the first iteration to be correct. I begin by writing something so I have something to look at and, more importantly, to step through. A full understanding of the problem and its solution evolves in that process of write code - write test - step through code - rinse - repeat. For me, that's more efficient and gives better results than to mull over that first draft and trying to get it right, the way you would on a whiteboard.
P.S. I found an error in this comment after I posted it, so I had to edit it. The iterative method rules.