When I use these criteria, I find that iTunes doesn't choose randomly from the least played songs, but backwards alphabetically.
For example: I have a playlist of 4-star songs, limited to 100 songs chosen by "least often played." If my least often played songs have 3 spins, then iTunes will spit them out beginning with the "Z" artists and go backwards through the alphabet, so that I get huge clumps of U2 or Wilco and no Beatles (until it's exhausted each 3-spin song from c-z.) Anyone else experiencing this? Anyone have a solution?