¿Has probado el rockplayer?. Tiene dos opciones (al menos en la versión que yo tengo), reproducción por hardware, en los que reproduce únicamente los formatos que soporta el Galaxy de manera nativa, y reproducción por software, y ahí reproduce bastantes más formatos.
Yo con este reproductor no he tenido problemas de formatos.