The activity of "reasoning-and-proving" is at the heart of mathematical sense making and is important for all students' learning as early as the elementary grades. Yet, reasoning-and-proving tends to have a marginal place in elementary school classrooms. This situation can be partly attributed to the fact that many (prospective) elementary teachers have (1) weak mathematical (subject matter) knowledge about reasoning-and-proving and (2) counterproductive beliefs about its teaching. Following up on an intervention study that helped a group of prospective elementary teachers make significant progress in overcoming these two major obstacles to teaching reasoning-and-proving, we examined the challenges that three of them identified that they faced as they planned and taught lessons related to reasoning-and-proving in their mentor teachers' classrooms. Our findings contribute to research knowledge about major factors (other than the well-known factors related to teachers' mathematical knowledge and beliefs) that deserve attention by teacher education programs in preparing prospective teachers to teach reasoning-and-proving.