I've now seen this three times, and have reproduced it at least once.

I go into the player and select to play music by Genre. I choose one of my genres, such as soundtracks. This brings up a list of something like 100 songs or so. I choose to play all the songs.

The resulting playlist, however, ends up being a random size. Sometimes it's twenty, sometimes 10. I even got one that was just 3 songs long.

I went into the menu again and tried selecting one of the songs that gets omitted, and it plays fine.

Any ideas?

Yeah, sounds like the query that's building the menu is fuzzier than the query that's building the results. This is entirely possible. Have you checked for case/punctuation differences in the genre field between the songs that appear and the songs that don't?