I think the CS Unplugged approach has a tremendous amount of potential, particularly with its intended audience (primary school). In my 3rd grade class in 1986, one day the teacher told us that she had a loaf of sliced bread in a bag, a jar of peanut butter, a jar of jam, and a knife. She asked each student to write, on a sheet of paper, instructions for making a PBJ sandwich. When all the students had finished, the teacher followed each set of instructions exactly as written. It was amazing and hilarious to see the literal interpretations. I remember it very clearly because I was one of the students who gave incomplete instructions, and it was a minor blow to my ego because I was one of the smart kids. It was also my first programming lesson.
For young students, simple activities like these (and other communication / language exercises like sentence diagramming) can have significant benefits later in their education. I don't think introductory CS education should be completely replaced by non-computer exercises, but it's no surprise that many HS students and college freshmen don't "get it" when the first thing they're exposed to is a pile of code.