The problem isn't that interview questions are too simple. Sure, quick weed out questions that can easily be sent out before an onsite interview make sense. But to have someone implement a red black tree, or implement some other algorithm that has an "elegant recursive solution" that is so far removed from any actual work the programmer would be doing is asinine. It's the same reason standardized testing is such a poor measure for many kinds of intelligence. It's forced and impractical- far removed from the real world.
Onsite interviews should consist of working with another engineer to look at a real problem the company is dealing with (or was dealing with in the past) to see how the interviewee approaches the problem and tries to solve it. It's not about reaching a solution per se, but rather how well the candidate works with the team and if her approach is the correct one.