Comment Try Scheme, or Haskell (Score 2, Informative) 663
If you really want a language "designed to teach programming and problem-solving", try Scheme or Haskell. Those are truly stable languages that will help students learn sound computer science principles, basic data structures, and programming principles.
Once that's in place, learning a "real-world" programming language is straightforward. No programmer should master only a single language.
And, yeah - C wouldn't be my choice for a first programming language either.