Eu acho que você instalou uma versão Windows do Java in Wine e tem precedência sobre o Java "normal" dos repositórios do Ubuntu, possivelmente apenas quando você abre o Minecraft através de um atalho na área de trabalho.
Você precisa remover a versão do Windows do Java (se você não tiver nenhum outro material instalado no Wine, basta remover / renomear o diretório .wine para ter certeza que desapareceu) e tentar executar o Minecraft do terminal com
cd ~/Desktop
java -jar minecraft.jar
Observe o parâmetro -jar. Certifique-se de que você pode rodar o Minecrafr desta maneira, e então você pode criar um atalho na área de trabalho como descrito no artigo linkado pelo MickStep.
Você também não precisa do Minecraft.exe, e não vai funcionar, nem tente.
Além disso, o Minecraft funciona bem para mim com o OpenJDK Java padrão do Ubuntu, então talvez você possa começar com ele e, se não der certo, instalar o Java da Oracle (mas, novamente, não uma versão do Windows)