Qual synaptic qual quê... o ubuntu tem uma das melhores ferramentas que existe para Gnome, o gnome-app-install, conhecido por "add/remove...".
Numa pesquisa por mp3 aparecem uma carrada de programas e um deles diz "Gstreamer extra plugins" e na descricao diz "codecs to play play mp3, sid, mpeg1..."... Facil, nao?
No Gutsy, basta instalar o pacote "Ubuntu restricted extras", na versão 7.04, não sei se tens esta opção, mas procura por Gstreamer, no add/remove applications, e pela descrição vê quais são os que necessitas.