If you resume playback, it will resume the playlist as it was last shuffled.
Basically, if you shuffle a deck of cards, put it down, and pick it up again, it's still shuffled.
You need to reshuffle your playlist, either by stopping playback and re-playing it (rather than resuming) or by choosing the reshuffle option.