I've been a programmer for over 20 years, professionally for over 15, and here are some of my observations:
(1) While programming talent might or might not be "innate", people rarely seem to improve substantially after their first few years of starting. I am a fairly decent programmer, but I don't think I'm substantially better - or worse - than I was a decade ago. I think that people tend to "get it" (or not) after a reasonably small amount of time (at most, a few years, often much less). You learn nuances, but basic ability seems to either gel or not fairly quickly.
(2) I think programming is a lot like math in that (a) many people think its hard, which becomes a self-fulfilling prophesy, and (b) most people have no idea how to teach it correctly. So a lot of people learn it, while thinking it's impossible to do, from inept teachers. Math isn't all that hard - at least a lot of it isn't - and neither is programming. But people think it is, so it becomes that way for them.
(3) Maybe it is a good idea to start with something simple. I've moved on to Java from C++, and, earlier, to C++ from C, to C from FORTRAN, to FORTRAN from BASIC. Starting with BASIC on a TRS-80 Model III, when the language and system were so simple, made it easy to understand all that was knowable, in a sense, so I never felt like it was too much to grasp.
(4) To me, programming is a lot more like communication - specifically, writing how-to instructional manuals - than it is like math. By the time I got out of grad school in aero/astro engineering, I'd had more math than 99% of the population. 15 years later, I rarely if ever use math beyond that available on a $2 calculator.
(5) I've read here how a lot of people can learn languages but not programming. To me, they're very similar - programming is simply learning how to tell the computer what to do. People who learn languages by memorizing vocabulary and grammar rules aren't going to speak as well as those who know what they want to say and learn the language progressively so as to be able to communicate their thoughts increasingly well. Likewise, I think you learn to be a better programmer by first conceptualizing what it is that you want to do, then by learning enough of the language to be able to do that, and then doing more and more difficult tasks. Just like languages all come down to expressions of thought in sentences and paragraphs, programs come down to subroutines, each of which has a specific task.
(6) "Object-oriented programming" is a phrase that is often horribly explained. Here's what it means (probably another horrible explanation): when given a task (program) to do, figure out the parts and roles - they're the objects. Figure out what the parts/roles do - those are the methods. Figure out what the subparts or things they "carry" are - those are the member variables. If you were building a house, you'd have your carpenters, plumbers, electrician, architect, painters, etc. If you were building a car, the parts are obvious. Object-oriented programming merely means to use real-world analogies to help you conceptualize what you're going to do.
(7) Crappy programmers are often crappy explainers. Someone who can tell you how to do something in a clear, friendly way will probably be able to program well. Someone who could spend an hour telling you how to turn on a light will make a bad programmer. If there's any innate talent involved, it's visible through how a person can explain something (or give directions) to a child. Or, more specifically, how good they'd be at recording a video to do that and getting a bunch of kids to understand it (i.e., anticipating problems and providing answers ahead of time).
(8) As others have said, programming boils down to figuring out what you want to do, then figuring out how to use the language to do it. Yes, Java has a huge library which can do almost anything you want it to do, but the library is all built (well, mostly built) with Java itself, so not knowing the library doesn't mean you can't do something, just that you might need to write more code to do it. But, if you know what you want to do, you'll get it done either way. Likewise, to talk to someone, first you have to know what it is you're trying to say, then you figure out how to say it. Some languages make it easier to say some things than others, but almost any language will let you get the idea across.
Ultimately, I think almost anyone can program, especially if they are taught, at least initially, by someone good - just like anyone can learn to talk. But some people are just better at it than others.
