Cambiar icono en tipo de archivo, Gnome

Intenta esto:

En ~/.icons busca en la carpeta de tu tema de iconos una carpeta que ponga mimetypes (a lo mejor los tienes divididos por tamaños, cada tema es distinta). Ahí deberían estar todos los iconos de todos los archivos, cambia los que no te gusten. audio-mp3.png es el concreto que te interesa.

Y si no pues en /usr/share/pixmaps están todos los iconos por defecto desperdigados...

Me pasó exactamente lo mismo que a ti, puto Real Player. Lo arreglé con el assogiate (http://www.kdau.com/projects/assogiate/ ), que creo que está en los repositorios (ahora no estoy en el PC de casa y no lo puedo mirar) y va bastante bien.
El RP no te cambia únicamente el icono de los mp3, también modifica otros formatos de sonido y vídeo.