I think the problem is more fundamental. Just browsing some of the comments already posted, I feel that the respondents are of two mindsets.
1. Those that feel one should quickly demonstrate that Java is easy to learn by having them type in a simple program
2. Those that feel an introduction to the abstract world of objects is necessary before any programming is done
Actually, there are some who would like both, as well.
Let's face facts. HelloWorld is a lousey way to introduce C and C++, let alone Java. It's time that object oriented languages were taught with the idea that the student better have the ability to deal readily with abstractions and if they don't they shouldn't be being taught Java.
We already have a host of so called programmers out there who have been taught how to hack solutions to problems using code, rather than how to abstract solutions for themselves.
The productivity of real problem solvers to rote problem solvers is 10 to 1, so why promote more of the latter? Java is an elegant language, and deserves more.