Debugging is a critical skill. Actually I would say more that troubleshooting is the crtitical skill. Someone should know how to define the problem (including what user information to ask for and what logs to look at), how to reproduce it, what data sources he has available to diagnose the problem and how to debug and then how to fix one thing without breaking something else. However, determining that during an interview is difficult.

I would give him a real problem to find and the opportunity to use the tools available and then ask what steps he took to find the issue or what else he might do if he was unable to find the issue in the time allotted. You are really looking for someone who attacks the problem somewhat systematically and who has more tools in his toolkit than just the debugger and google (except at the Junior level when he should at a minimum try both of those (someone who can't think to try those two things is probably not competent or at least I wouldn't take the chance on him) but probably doesn't have a lot of advanced troubleshooting tools yet).

I would give more weight to troublshooting skills than the answers to puzzles (well I wouldn't ask those at all) or to demonstated programming skill. I have rarely seen a developer who can troubleshoot well who can't also write good code or do the needed fixes. I've seen plenty of people who can cobble some code together to geta "Working" product but couldn't fix a problem if their life depended on it. Mostly becasue they don;t actually understand what they are doing or understand the problem they are trying to solve. Good troublshooters know how to identify the real problem not just the symptom. An das such they know what questions to ask to define the problem for new development as well.