If you were using the "Least Recently Played" version of the shuffle, and those three tracks were part of an album that had not been played recently (or had not ever been played because it had just been uploaded), then the shuffle is working as expected.