Problem-solving is unquestionably one of the most important skills; other skills such as writing efficient code, effective communication, working with a team, and many others, are also very important.
It's impossible to say any one skill is the MOST important. The subject of Programming for Problem Solving aims at developing problem-solving skills and the skills to create programs in any language for their implementation. Most of the books on programming teach problem-solving. Unfortunately, there are limitations on what can actually be taught. It is mostly learned by practice. The point that I wish to make is to get students to see the problem-solving process in action.