For comparison, I heard that people who start with functional programming find it quite intuitive. The hard part isn't learning a new paradigm, but "unlearning" the old one.

(Also I hear they're more than a bit sad about how crude procedural programming is! But unfortunately I came at it the other way around, so my standards are permanently lowered ;)