This is perhaps the biggest obstacle for people who are trying to teach others to program - and so I agree with you here.
However, it does seem like there are some people who will just never be able to pick it up - even though they are demonstrably smart in other areas.
There will always be those with exceptional aptitude. But if you must be exceptional to simply understand a subject as broad as computer science, that's a problem with how we conceive the science.
The Romans thought multiplication was really hard, too. Exponents were literally unthinkable. We know better not because we're that much smarter, but because we have a simpler and more powerful way to think about it.
I can conversationally say to fellow computer scientist "I organized the pieces of data into a red-black tree" and that's totally programming language agnostic and conforming to English syntax while still requiring a hefty amount of CS knowledge to grasp the actually meaning of what was said.
She can't or won't make the mental leap from basic algebra skills to variables and functions. Mentally unrolling loops or recursion, forget it. I don't even bother trying to explain data structures like stacks and heaps. How a programming language [that's mostly human readable] gets turned into machine interpretable information is black magic. She even took an intro to programming class as part of her degree, so I'm not the only teacher who's failed at the topic. It can really be frustrating at times because I have a respectable knowledge of geology and its industries and can conversationally hold my own with her and her peers, but she can't reciprocate at all with my peers.
For my sanity, I've always assumed some people just can't readily grasp the abstract symbolism and recursiveness programmatic thinking requires.