It's also not (quite) obvious to me why people think that Perl is interpreted and Java isn't.
It's obvious to me: because they have to run javac before they can execute Java code! As we know, Perl does this step implicitly, and Perl's compiler is so much more efficient than Java's that no one even knows it's there unless they bother to learn something about how Perl works internally.
The bottom line for anyone who doesn't already know this: both languages compile to bytecode and then interpret that bytecode. This is also how modern versions of PHP and Tcl work. So, explain to them that Java is no more compiled than PHP is, and see what they make of that.
Also, note that while Perl CGI has to do the compilation step every time, mod_perl and similar persistent technologies (and equivalent for PHP and Tcl) just keep the bytecode in memory after the first time it is compiled.