Intentaste con el PowerAmp? Trae muchisimas opciones para todo, para mi es el mejor reproductor para Android.
Otra cosa: todas las canciones tienen su informacion en los tags? Sino supongo que los reproductores lo enlazaran con los datos de la carpeta contenedora. Saludos!