I don't think they'll ever move away from Java. I don't think Minecraft requires something quite on the scale of a complete rewrite, but perhaps starting from scratch and pasting in bits and pieces of the original to save time would help things.

They are working on rewriting substantial portions of the codebase, but unfortunatley Notch didn't hand it off to the most skilled maintainers and they aren't making things much better.

they have already moved away from Java via JNI for some aspects of the game, like openGL 2.0 support.