I think a FizzBuzz type problem is a great way to see the candidate in action. People do get the jitters in interviews, but if you don't ask the candidate to actually write code then you haven't really interviewed them.
I try to use the same basic outline for all programmer interviews, so that I can fairly compare candidates:
1) Go over the candidates resume, have him or her answer basic questions about the projects they've participated and the companies that they've worked with. Try to get a feel if they've work in an environment similar to yours. For example, if you're in a startup with no rules and the candidate came from IBM or the DoD then you need to figure out if they really would be happy in a less structured environment. Conversely, if you are in a large organization with lots of rules and procedures then a programmer from a 10 person startup might not be happy submitting to your management hierarchy.
Try to get a feel for the actual work the candidate did. This is a good time for one or two 'tell me about a time' questions, i.e. 'tell me about a time you had to quickly solve a hard problem under pressure'.
Ask 'what are your weak points?'. If he or she says anything other than 'I like to hit people who ask really stupid questions in interviews' then end the interview there.
[ETA] I always ask for candidates to bring sample code, this is where I have them show and explain their code to me. The best candidates will actually whip out a laptop and demo something.
2) Have a list of the skill sets that are important in the position you are filling. Ask the candidate to rate his skill in each area from one to ten, with one being 'never heard of it' and ten being 'I invented it, or wrote the seminal book on it'. What you're looking for is honesty and logical consistency. The absolute values of the answers aren't important except for the zeros, ones, nines and tens. An excellent programmer might not be familiar with some tool or technique you use, but if he or she is honest and smart they'll come up to speed quickly.
3) Have a list of technical short answer questions on each skill area you asked about. Don't waste time asking questions about the subjects the candidate self-rated as low, drill into the areas where he or she claims expertise. Try to think of questions that come up in real world programing that are typically glossed over in academic study.
4) Think of a design and implemenation problem you've had to solve. Ask the candidate how they'd handle it. Since I do mostly desktop applications, the question I like is 'You need to add an application update function to a desktop application. How do you implement it?' I'm hoping he'll describe an updater that includes security and reliability considerations. You're looking for signs that she's had experience in solving design and implementation problems in the real world.
4) Give the candidate some programing problems, starting with something like FizzBuzz, followed (if he or she can do that) by more difficult problems until you realize you've passed the point of diminishing returns. This is also your best chance to see if the candidate is someone who's personality will fit into your team, something I consider of primary importance.
If you have more than one interviewer then these steps can be parceled out.
Good luck.