Ah, I see. The title of your post indicated that you had already decided that step 1 was the problem, that's why I pointed out the "two steps" issue. But now that you confirm that it wasn't step 1 at all but step 2, we can address the problem.
Unfortunately the best way to solve this problem is to stop using the console, as in many environments it isn't really designed for proper Unicode support. And it doesn't help that in Java, until recently, you had to use System.out to write to the console, and System.out is a PrintStream, about which the documentation says
All characters printed by a PrintStream are converted into bytes using the platform's default character encoding.
However in Java 6 there's the java.io.Console class, which gives you access to a PrintWriter for the console. This might work better for you, unless you were already using it.