Olá amigo.
Pelo que notei na atualização, o ubuntu desinstala programas que não são default, ou seja, padrões do sistema operacional, gxmame é um deles, muito embora você tenha instalado ai, dê uma conferida pelo Synaptic (ou pelo Adept) o programa principal do gxmame está instalado ou até mesmo ele, o nome é xmame, se ele não tiver instalado ele não vai rodar mesmo.
Posta ae os resultados!
Abraço!