Por algum motivo estranho, eu tive o mesmo problema até que eu instalei a versão anterior do java, OpenJDK-java-6-runtime. Tente fazer isso, e o minecraft funcionará muito bem para você também.
use: (no terminal)
sudo apt-get install openjdk-6-jdk
para instalá-lo e, em seguida, clique com o botão direito do mouse no arquivo de minecraft e selecione run with Java 6
Boa sorte!