Eu tive o mesmo problema, apenas com a versão gtk. Acontece que em alguns repos (eu tentei Lubuntu e Synaptic), apenas o front-end GUI está disponível, sem os subprogramas reais, ou seja, mp3gain, vorbisgain e aacgain. Ir ao site do mp3gain, como você descobriu, é inútil, pois você só encontrará binários do Windows. De outro post link , ficou aparente o .debs para mp3gain pode ser encontrado (em várias arquiteturas) no seguinte link:
Eu baixei deste arquivo e instalei usando o gdebi e funcionou para mim.