Hi Dave,
I know that you said you have "Shuffle" switched off,
presumably from the Main Menu and switching off "Shuffle songs",
but there is also a "Shake to Shuffle" feature - could that still be ON ?
Here's a link to the Apple instructions for the feature :
Shake to shuffle"Enable or disable Shake for shuffling songs :
Choose Settings > Playback, choose Shake, and then select Shuffle or Off"
