One thing I learned a while back at one interview (or rather, I just worked it out after experiencing it a few times) is that I find it much harder to think/code on a whiteboard. I don't know what it is, but it seems much easier for me to sit down with a pen and paper and work things out.

I mean, still coding without a computer - but it's something about standing up at a whiteboard. Maybe it's normally not so bad for me, but with the pressure of an interview, it's bad enough to give me problems.