Parece que algo muito mais profundo do que o java está errado aqui. Sou muito novo no Linux para descobrir o problema exato, e muito menos resolvê-lo. No entanto, parece que há algum vazamento de memória acontecendo no próprio linux mint.
Não importa o Java que eu executo, mesmo que eu execute o Java que vem com uma nova instalação do Linux. Além disso, eu tive esses problemas com a minha memória RAM. Em tempos aparentemente aleatórios (estava sempre a fazer o resto), o uso da minha RAM passava pelo telhado. Eu costumo usar cerca de 1,5-2GB, mas nessas horas, dentro de um minuto, o sistema usa o total de 6GB, e enche o meu swap para outro 4-7GB (de 10!) Também, antes de tudo se acalmar novamente ( RAM vai para 2GB e troca para 0,5GB) em um instante.
Embora eu não tenha resolvido diretamente o problema, decidi (como último recurso) mudar para o kubuntu. E, de fato, não tenho nenhum desses problemas agora. Java funciona e o Android SDK também.