Like everything else, that is a matter of practice. Coding on paper or whiteboards is a skill you can become proficient with. Get a whiteboard, get something like skienna's algorithm book, and start practicing coding problems there while talking through what you are doing. Start simple then go more complex. After enough hours, this will become second nature. I realize this is a silly exercise, but if want to work in the circus, sometimes you have to jump through hoops.

I don't get the big deal about whiteboard coding and such. I have to write code on paper for my CompSci class exams and it's never been really difficult. If it were PHP it would be though because it's hard to predict the argument lists and function names.

Same here. Ask me to build a distributed web crawler with a Lucene-based search engine in Rails or whatever, I can code it in a month. Ask me to write a function that does something stupidly simple like converting a character to its ASCII equivalent, and I'll fail.