Eu tenho o mesmo problema, eu tentei instalar codecs para ver se esse era o problema e eu definitivamente posso reproduzir arquivos m4a no Banshee, Rhythmbox, etc. Parece ser apenas uma questão específica do Spotify. Eu acho que nós vamos ter que esperar até que os desenvolvedores passem para o GStreamer ou algo assim (ou até mesmo seus próprios codecs, eu não me importo, contanto que funcione.)
Desculpe, não pude ajudar muito mais.