EDIT: Oh, just remembered you can program Lego Mindstorm in Java. Although I don't know how user-friendly that environment actually is, it's not the one Mindstorm comes with.
Long answer: The C++ dialect you use when getting started on Arduino is fairly short on C++-isms and is designed to be simple, straightforward and familiar for people who used the Java-based Processing framework.
So it wouldn't be a big stretch. At a guess I would even say Arduino is very much simpler than Java for a total beginner, talking in terms of number of concepts required to build something simple but useful.
We have Mindstorms and have switched to RobotC from CMU rather than using the graphical programming approach. That works well enough. It seems that all middle and high-school programs that do Mindstorms stay with the graphical programming approach which is a shame because it makes doing anything serious very difficult.
If Java on Arduino isn't a possiblity, are there Arduino-like boards for Java?