should a programmer need good debugging skills?
Yes. That said, I would ask you to consider the methodology in the interview (i.e. quiz / test-style) less than perfect (okay, flawed) in that many people find code on paper a strange, unfamiliar experience.
Since debugging is a process, not the answer or result (e.g. the mistake), I would suggest using an interactive dialogue or discussion as a better means for assessing a candidates debugging abilities. While most people use an informal ad hoc system of debugging, good candidates will have a similar pattern in general, of asking questions to gain understanding the system or assumptions, and requirements, then isolate the problem (often divide and conquer), and methodically compare the code to the requirements, and evaluate expected input/output, rather than a willy-nilly changing a bunch of things at once haphazardly until it works.
I also express reservations about puzzle problems during interviews, particularly in written form, as if the candidate doesn't have the right assumptions of framework of reference (the trick), the puzzle maybe unsolvable to them. I.e. Many interview puzzles suffer from having a single correct path, whereas life is complicated and the most creative thinkings are the ones who take surprisingly novel approaches to solve a problem that may not worked with a given particular pre-cooked puzzle, with an expected solution. It's like expecting all trumpet players to play jazz. This can be managed by asking the question as a non-confrontational (pressure can confound creativity) interactive discussion. Again, to me, the answer is secondary to see a good thought process being expressed. You will likely need to ask them to think out loud, but this tends to be more productive in my experience.
I haven't read or evaluated Zeller's Why Programs Fail, but I can recommend Debugging by Agans as a short, quick read that can help solidify the ad-hoc debugging process into a more structured, concrete, and organized effort, which can help to be more efficient at debugging. Also print out a copy, and hang it at your cubicle or workaround, the Debugging Rules poster, it's a perfect reminder for those bad days where nothing seems to go right. I have few bad days, and spend less time actively debugging (read: scratching my head in confusion) by trying to follow them in spirit if not in letter.