Any language which is useful for showcasing the fundamentals of computer science is fine to teach the fundamentals of computer science, including BASIC, if what we're talking about is a variant of BASIC which implements object orientation, recursion, referencing and self-referencing, and the essential data structures. Line-numbered BASIC doesn't do that, but Visual Basic and implementations similar to it, like Object Pascal, do.
Beginning programming is not about the nuances of CS; it's appropriate to use a language which hides memory management issues and doesn't force programmers to think about symbol case or even much about scoping.
But even after having said all that, if what we want to do is raise a generation of programmers who automatically think about things like manycore issues before they're juniors at a University, staring with DSL's or F# (I know it's not a DSL) might be just the thing. I don't necessarily agree that C# or any C-based language is a natural endpoint to any of that.