I have disabled the "shuffle on shake" feature of my iPod Nano 5th gen, yet occasionally this still happens. I've noticed, for example, if I have it connected to the aux jack in my car while driving, if I hit a speedbump or pothole, it activates shuffle mode. I've double-checked the setting to the point where I'm beginning to feel a bit OCD. I know this is older hw, but is there some way to permanently disable this feature on my specific device?
Have you tried running a full restore of the iPod? I know it's kind of a last ditch thing to do, but it seems like you may be experiencing a hiccup in the hardware. Also, make sure you've got the latest update from Apple installed on it.