I worked as teaching assistant for the computer science at a college and I have to say that, for most people, programming is *not* something that they will just pick up. I worked the computer lab for the introductory programming course and the majority of the students had to work very hard to learn programming.
The point at which students initially had difficulty varied too. A surprising number had trouble with concept of a for loop. All of those students did make it past that though. What all of the students that had significant trouble with the course had in common, though, was the ability to generalize. They had problems with coming up with simple algorithms to solve simple problems. They could describe how to solve for very specific circumstances. Indeed, it seemed, most of the students could code a solution to a very specialize specific scenario, but, at least initially, not the general case. Many student improved greatly in this regard by the end, but a decent number still had issues (and I am only considering the ones that put forth effort in the course).
Most of the students having issues could somewhat understand logical concepts. They could debug simple implementation issues, and they could usually look at other people's working code and explain what the code was doing. These students lacked the ability to think abstractly and apply logic and their learning to new problems where the steps to solve the problem weren't laid out for them. I believe it is the same issue you see in middle/high school math classes where many students can manipulate equations just fine but have problems with solving story problems.
So, I do believe learning (proper) programming at an early age would benefit people. They would get more practice with thinking abstractly and have a venue for seeing practical and essentially immediate results.
Also, I don't thinking learning to program would have to supplant other courses. It could be be used in addition to other topics. For example, children could be give a code that performs math on single digits numbers and then modify to handle numbers with multiple digits. Imagine programming long division and handling remainders. I think implementing the code for this would allow children to understand numbers and math at a deeper level.
Ensuring programming was taught to everyone would have some benefits for employed programmers and to society in general, also. Right now, you see people in forums making comments about the sad state of some particular piece of software and how easy it should to fix an issue or how some problem should be easy to solve with a computer and why don't the programmers just code it up. People would come to realize the difficultly of creating a good program and what trade offs must be made for a program to be made quickly and relatively cheaply and perhaps they would decide for different trade-offs.