This problem with Java has been thoroughly addressed by the good folks at www.bluej.org, who created the BlueJ IDE for Java specifically to enable them to teach proper OOP in Java at a CS101 level. They are a group of CS teachers and researchers from (IIRC) Monash University in Australia.
On the other hand, perhaps this kind of problem is a really good reason not to use Java as a CS101-level language. Maybe the difficulties involved in teaching proper programming using Java simply show that Java might be better used as a second or third language, rather than the first language to which a budding programmer is exposed. After all, MIT teaches programming using LISP, right? "Structure and Interpretation of Computer Programs". And Python is also being pushed as a great introductory language, as well.
Java's wide-spread popularity in the business world for server-side programming does not automatically make it the best choice for all purposes. I think we should remember this principle when contemplating CS curriculum, something that affects the future of, well, darn near every aspect of life (at the risk of sounding somewhat melodramatic ;).