I felt bad about my nervousness in interview situations too, so I started taking improv classes. Now interviews don't give me any performance anxiety at all; once you've performed in front of a large audience with no idea what you're going to say or do, it makes interviews a cakewalk.

And remember, even though the primary skill you're interviewing for is coding, they are also testing you for communications ability. Being able to clearly and concisely explain what you're doing is at least as important as being able to get things done.