Your conjecture, that problem solving is innate and cannot be taught, does not hold water. It does come more easily to some people than to others, but problem solving skills can be developed in all students. Here are some things the instructor can and should do to help this happen:
The instructor should structure things very clearly, and train students to go through a sequence of steps despite the anxiety they may feel.
Allow sufficient time. If you pose a warm-up problem at the beginning of class that you think will take three minutes, and at the three-minute point 20%, or even 50%, of the class is finished, you didn't give it enough time.
Show worked examples, explaining how you got from Point A to Point B.
Show the students how to recognize certain patterns. (So as to reduce the problem down to one they've already solved.)
Be clear about what, if anything, needs to be memorized.
Check each student's mastery of the basic procedures and understanding of the material that has been taught. Any vagueness in the student on the basics will create stumbling blocks that will interfere with problem solving.
Assign regular practice problems for doing at home.
Model positive self-talk.
Exactly what the sequence of steps will look like depends on the type of problem to be solved.
Example 1. Factoring a quadratic expression. Your sequence could be:
(a) Check if every term in the expression is a multiple of the same thing (consider both letters and numbers).
(b) Check if it's one of the special cases (perfect square, difference of two squares). (You have to get students very comfortable recognizing these special cases by introducing them early in the course, and coming back to them plenty of times, in different guises, and you need to make sure students are seeing the pattern.)
(c) Analyze the signs to decide if you need two factors with a positive sign or two different signs.
(d) Write down the various possible factorizations of the first and third coefficients.
(e) Try out some combinations. When you have something that you think will work, put in the signs (positive? negative?) and then multiply to see if it's working.
(f) If you get stuck, write a table of values (x, y) and draw a rough graph. See if you can discover, by looking at the graph you drew, where the curve crosses the x-axis. If necessary, fall back on polynomial division to see if your guess works, and to find the other factor.
Example 2. Coding or developing an algorithm.
(a) Sometimes it's helpful to draw a rough diagram showing input and output. Starting out with a drawing can be quite freeing.
(b) Try out a particular input and make sure you know what needs to happen to it in order to yield the desired result.
(c) Write down some processing steps. It's okay if it's in English initially.
(d) Try out your algorithm or code on some input data. If that seems to work, try some slightly odder input data. Adjust the procedure if necessary.
(e) Reread the problem to make sure you didn't misunderstand something.
Example 3. Word problem.
This has some similarities with the other examples; rough sketches can be particularly helpful here.
In addition to ideas from above: At the end, check the units, comparing the problem statement against your solution.
Example 4. Writing a proof.
Break up the problem into smaller parts if possible. Write down what the general goals are, i.e. what you need to prove.
The beginning proof writer would do well to write down, at each step, what needs to be shown. In the beginning, verbosity can sometimes help maintain focus. If appropriate, draw pictures, try cranking out the results for some simple input values, and then with more complex input values.
If the student gets stuck, s/he should be trained to write down all the facts given in the problem, and any possibly relevant theorems that have been learned so far.
Don't be afraid to jump temporarily to an intermediate step and, for the time being, assume we can show a certain result that will help us get to the end goal.
Beginning proof writers can benefit greatly from using a two-column format, where for each and every assertion listed in the left-hand column, some justification must be written down in the right-hand column.
At the end, reread the problem.
General comment: In the U.S., the key places where students are typically expected to make a quantum leap in problem solving:
two-step word problems (usually first assigned in 4th grade of elementary school -- example: "The area of a rectangular doghouse floor is 15 square feet; the length of the floor is five feet; find the perimeter of the floor of the doghouse" found at https://www.engageny.org/resource/released-2016-3-8-ela-and-mathematics-state-test-questions)
geometry (usually taken in 8th, 9th or 10th grade of secondary school)
linear algebra (STEM students usually take this in approximately the sophomore year of college)
For sociological concerns about students' general difficulties with problem solving, it can be helpful to identify at what points in the educational system the quantum leaps are expected to occur. When working with a particular student, it can be helpful to identify at what point his or her difficulties began.