[Gimli[2BV!2B]]

Non è un mp3.
Si tratta quasi certamente di un wma di una qualsiasi versione; come puoi intuire i wma non sono propriamente liberi, quindi, come hai detto, il loro codec è nei w32codecs.

Per installare i w32codecs in Ubuntu credo che tu debba aggiungere il repository Medibuntu.

Ecco la documentazione ufficiale che spiega come aggiungerlo, quello che contiene, ecc...