I find many of the interview puzzles that people have posted on the Web that they've encountered at the Big Name companies as often a bit silly. Having said that, asking software developers to implement a solution to a common programming problem - "navigating a tree using recursion", etc. is perfectly reasonable. I've found more than a few software devs who have great looking resumes but who have no idea what recursion is, what a tree is used for as a data structure, etc. And I consider this the basic, easy, 1st year undergrad type stuff.
If there's an undercurrent to all of the comments here, it's that we still don't really have a good way to sift through the good from the really-not-so-good developers quickly. The programming tests and puzzles are a proxy for this and they only work so far - some people like to think through issues more before coding, or tend to freeze under this on-the-spot pressure. Doesn't mean that they aren't a good, competent developer you'd want on your team; my experience is that the guys who blurt out very quick answers can sometimes write the worst code.