I was one such potential CS student a few years ago. I majored in something else, but got back into CS quickly after discovering Perl. Perl got me inspired to take a bunch of CS of courses such as Computer Architecture, Compilers, and Operating Systems. I'm now entering the work force as a Computer Scientist after graduating this May thanks to the lack of graduating CS students
I think that many potential CS students are discouraged by that Introductory course. I think an introductory course should not teach Java as the first language, but a scripting language such as Perl or Python. Scripting languages allow people to get "feedback" from their programs much faster, not to mention that they are easier to learn and that an interpreter is much easier to conceptualize vs. a compiler (Intro students cannot be assumed to know or have to learn what machine code is; let the Architecture course take care of that).