azoapes
Fibonacci is not such a problem. It includes declaring one argument, a handful of variables, one for loop, a couple of assignments and a return statement. And he could not do this with open and explicit guidance.
As he was applying for a senior backend developer position, I can only conclude that morphing complex data structures and calculating shopping carts with taxes, rounding and campaign deductions will be a problem. Maybe I'm wrong, and I should mention that there were additional interview steps and questions where my interview partner didn't have confidence in the candidate, but I really feel that this excercise tells me something. And that's the problem with these kinds of interview techniques I guess. That they do feel very relevant.
This excercise in particular took a little more than an hour, because even though I explained a few solutions in various ways he had a hard time actually completing any code. I wrote a whiteboard solution and explained it using arrows and walk-through examples, but he couldn't translate the solution into actual code (using a language of his choice). In order not to break the hour limit we ended up with me writing and explaining code one line at a time for him. I reassured him that it's okay that he can't come up with the code right now, we're not evaluating the result etc.
I turned this candidate down. I feel that while my methodology (close to OP's) has flaws, it does help me with filtering out the worst candidates. I simply can't hire someone that doesn't manage to, with an unlimited amount of help and a generous timeframe, code a Fibonacci sequence in his/her favourite language.