Enquanto você pode instalar a dll em falta usando winetricks
e usar a versão do Windows do Visual Boy Advance, há de fato uma versão nativa do Linux nos repositórios Ubuntus, que eu recomendo usar em vez do arquivo exe.
Para instalá-lo, abra o aplicativo do terminal e insira este comando:
sudo apt-get install visualboyadvance visualboyadvance-gtk
Deve ser ouvir no menu de aplicativos depois disso.