Solving complex problems is critical to educational leaders' ability to achieve improvement in schools. Much of this problem-solving is carried out in conversations with staff. This paper draws on theories of collaborative problem-solving and interpersonal effectiveness to examine the behavior of leaders in such conversations -- in Norway and New Zealand. Analyses of conversation transcripts of 17 Norwegian and 18 New Zealand leaders revealed that only half of the leaders overall engaged in advocacy, inquiry, and collaborative planning behaviors. Slightly less Norwegian leaders tended to engage in open and collaborative problem-solving behaviors compared to their New Zealand colleagues. New Zealand leaders, however, seemed less open and more directive in proposing solutions. Overall, we observed a lack of deep, critical inquiry and discussion of problems and their causes, which is likely to stand in the way of effective problem-solving and school improvement.