At the risk of starting a semantic flame war, I have to say that I personally prefer "lexical" because it is a better description of their actual scope -- from the point of specification to the enclosing right curly (or the end of the file).

If you search "private variable" you get things that are much more widely visible than Perl "my" variables (e.g. Java private attributes). I worry that a newbie coming from such a background may be confused by the use of "private" into misunderstanding the actual scope of the variable.

Package variables are in fact not lexically scoped, though the ability to access them by their unqualified name can be. Even if you turn on warnings, you can still access them outside the scope of the "our" by fully-qualifying their names. Consider the behavior of the following one-liners:

perl -E '{ our $foo = 42; } say $foo'

perl -Mstrict -Mwarnings -E '{ our $foo = 42; } say $main::foo'

Perl is a large, complex language, and we need to provide ways to help newbies find a way in. My concern with s/lexical/private/g is that it may teach newbies things they have to unlearn to progress.