The "No One Believes Anyone Can Actually Code" point is right on the money by my anecdotal experience. Just a few weeks ago I was asked to implement FizzBuzz in an interview for the first time in my 15 years of engineering! This was despite having a large amount of verifiable open source Haskell projects.
I usually ask a trivial problem like this. Not really to see if they can code (I have had one or two people fail here though), but more to serve as a conversation topic. Why did you do this? How would you do that? etc...
Ask me about your current problems, problems the person filling the position would need to have opinions about. If nothing else, maybe I could crack a tough issue for you that would have material value.
I've given FizzBuzz, and I've done FizzBuzz. It's hard to do it/get it and not feel like there's some degree of insult involved.