C is actually a relatively simple language and a good choice for beginners.
I agree that you need to teach general logic principles which are language agnostic, but if you do this in the context of C++, the beginner is bound to waste a lot of his time fighting irrelevancies in the language.
I agree that C++ is a complicated language, specially when you use Boost or Tools.h++, or the even make things worse. But when you teach beginners to code in C++ and only utilize STL, I believe it would be an interesting and challenging course. Plus, in an entry level course, you only need to introduce the basics of programming, which are (in an abstract sense) general logic principles and language agnostic.