This is a known bug, or really more of a design flaw. The random song picker will select songs that are higher up on the popularity list in general. However, if you have over 5000 songs, the popularity list will have little meaning until there are at least 5000 plays on the jukebox, and in all likelyhood many more, since most songs will have 0 plays until then. Of course, the secondary sort is alphabetical, so the songs higher in the alphabet get played.
Ths is fixed for the next version; in that version the playcount of the song a quarter of the way down the popularity list is checked, and if it hasn't had at least two plays it ignores popularity. Until that is released, set RandomSongPopularityPreference = 0 in jukebox.ini. Ths will get you a true random spread in radio mode.
--Chris