I really did learn programming via SICP-style scheme, culminating in writing an interpreter (but not actually using SICP - I think it was the Schemer's Guide). I did it in a class, which may make it very different. I (and my teachers) think an important goal in learning to program, a hurdle that most professionals fail to clear, is to believe in the program as a lawful calculation, rather than a willful spirit. Syntax exaggerates this problem. Purely functional languages help by making it easier to simulate the code. Things like Project Euler may play a similar role.
Actually, before scheme, I wrote a few simple programs in basic. But they were only primitive recursive and while I could understand more complicated basic programs, I couldn't imagine writing them.

I would recommend a class based on SICP. Without the discipline of a class, it's probably not the place to start. Yes, the key is not reading the book, but doing the exercises.