Speaking as someone who has taught general problem solving, yes people absolutely can learn it.

Well, they can learn general problem analysis. Actually solving a problem pretty much always requires domain-specific knowledge.