Такая проблема наблюдается не только у вас, это нормально.
Генерировать по-настоящему случайные числа - это очень сложная задача. Обычно, для получения случайного числа берут одно или несколько входных значений, предположим, количество песен в плейлисте. А потом производят с этим числом какое-нибудь математическое преобразование. И если разработчики схалтурили при выборе преобразования или при выборе входного значения - «случайность» случайных чисел будет невысока и в случае плейлиста, вы начнёте замечать, что некоторые песни попадаются чаще. Я такое замечал на старом mp3-плеере. Если же проблема на телефоне - попробуйте сменить программу для воспроизведения музыки.