If you mess with this program, you can see that the 150-song case is always going to look funny in a shuffle even if it's completely random. That's just too few songs to get a decent distribution. 1000 songs is better, assuming the artists in question are evenly distributed.

However, if the player is genuinely doing a least-recently-played rather than a random, then I would think that would be a bug.