iTunes not playing all songs in a playlist
iTunes defines the random order of the tracks when you first specify set "Shuffle".  (This is so that the skip forward / backward buttons work in a reasonable manner.)  If you never turn Shuffle on or off, that order is never changed.  Just disable and then re-enable Shuffle to get a new random order of tracks.  

For more detail, see Why isn&#39;t iTunes shuffle random?.