I don't have a problem with paper - I just feel like it would work against a candidate - not because "Oh...they used paper", but because some of the things that I think are signs of a good candidate don't show through.

I've never interviewed a candidate that asked me to use paper, so I can't be sure - it's just my instinct.

It might be completely biased though - I far prefer to use whiteboards - I love the space, I love how easy it is to erase without a trace. I can throw thoughts up there and the manipulate them.