If you have internalized the concepts Haskell is built on (to the point that you don't have to think about them), then Haskell can be as simple as any other language, maybe even simpler. But if you have to still have to think about the underlying concepts, Haskell probably is more cognitively demanding.

That's exactly the point, yes. People just have to properly learn the language.

I'm not sure it's that simple. I suspect (but cannot prove) that some people are naturally procedural thinkers, and others are naturally functional thinkers. Haskell just makes sense to some people - and not to others. To say they "just have to properly learn the language"... I could say the same about you and C.

Assuming I'm right, can the naturally procedural thinkers really learn to use Haskell? Probably yes, at least most of them. Will it ever be as easy to them as procedural programming? Probably not. What will that "not as easy" look like? Greater cognitive load.

I am aware that all of this depends on my opening assumption being correct...

That's an interesting assumption.

It might be true to a degree, yet I reckon the problem lies in CS teaching. A vast majority of programmers seem to start with imperative languages, hence they are more familiar with the procedural paradigm, and when they encounter functional code it seems alien and difficult to work with.

That's why I wrote people “just have to properly learn” functional languages. But your hypothesis is probably true as well.