I can corroborate that for people with no prior programming experience, but a significant math background (engineers, stat and math majors), the statement "x = x + 1" is befuddling to them. They have no concept of time in a sequence of imperative statements. That is, they don't intuitively understand that statements get executed, and that the state of the program changes (potentially) after each statement. It takes real effort on their part to internalize this idea.

Now, I'm sympathetic to your final paragraph, but having never taught functional programming to anyone, I can't corroborate it. Personally, I went through something similar when first learning how to think functionally.