No one remembers how they learned things at an elementary school age. I think the reality is our understanding of concepts was very muddy at that age. Thinking about abstract concepts still requires a lot of context that kids don't have. I'm not sure kids can really grok the importance of the abstract concepts in programming, and I'm not sure that importance can be taught directly. I think the ability to grok those concepts comes from a bank of general world knowledge that must be slowly built up to in adolescence.
Teaching programming early on may give kids a few worthwhile mental tools, but I'm not sure we can expect kids to get any magic "fluency" benefits the way we can with language. The risk of turning kids off programming by forcing them into it early may outweigh the benefits.