Tu solución se llama xmms-aac, un plugin para XMMS que es parte del proyecto FAAD, el mejor decoder de AAC con diferencia (y libre). Me imagino que la mayoría de las distribuciones deberían tenerlo disponible, así que prueba a buscar con el instalador de paquetes de la tuya (urpmi, apt-get, emerge...).
Saludos.
