I think I perform poorly in these sorts of interview, because in the wild I never solve programming problems by writing things on a whiteboard or on paper (unless it's a geometry problem), and I also frequently use external references like books or the internet which are never available in the interview setting. Another problem is that I almost never debug code exclusively by staring at it on paper.
I guess like with everything, it's about practice. It's difficult to be good at something if you never do it. It is a bit of a pain since you never actually HAVE to do in your normal work. It is however worth practicing if you know you're going to be put in a situation where this will be an issue (such as an interview).
If you practice enough, you will get better at it and I do believe that it is certainly better to practice on your own rather than failing multiple interviews and using that as 'practice' :).
