I would agree - I'm current in a college CS program (I have ~6 years of programming experience already, so the introductory stuff is a breeze). The very first programming class we took was "Intro to Object-Oriented programming in Java". The irony is that a good 3/4's of the final projects people turned in where just a big mess of procedural static methods and global variables all shoved into the single 'required' class to hold main(). There were some who after going through the class understood OOP a bit more then they used to, but those were really just people who already had some programming experience. Those who came into the program with no experience were still trying to figure out the basics of procedural stuff ('This is how a for loop works', 'this is an int, it's not an object', 'i = i + 1 is a valid statement', while() vs. do while(), etc...) (And are still trying to figure that stuff out even now, though now a bit more complex issues, a year later, since it was never really taught that well)
I think the biggest thing that stuck-out to me as being utterly wrong with teaching Java and OOP is that you're forced to talk about references/pointers extremely early on, when most of the students don't have enough grasp on the core language to understand them conceptually (And really, who understands a reference/pointer the first time they heard about it? let alone 2 months after starting programming).
I honestly think starting off with C would have been better, and I don't view C as a good beginners language. But C itself has a pretty simple core language, and writing small procedural programs in it isn't very hard to conceptualize, so it requires a minimal amount of hand-waving to get simple programs running. (Hello 'public static void main(String args[])') The biggest hurdle would probably be string handling, as it's an array of char's. If you're not concerned with buffer overflows though, simple stack-allocated arrays work fine for tons of simple introductory programs, and <string.h> provides enough to get by without messing with any pointers.
Starting with C would be good, but only if the teacher constantly supervises and reviews the code that gets written by the students. Beginners will inevitably do mistakes as they are learning, and the leaky abstraction between C and the underlying architecture would punish these mistakes mercilessly. Writing correct C code is one thing, asking "why is this language broken" because you returned a pointer to a local variable is another.
