Could it be faulty mechanics? Also, you might try manually reapplying the firmware, in case it’s a firmware glitch–see the firmware upgrade sticky thread at the top of the forum.
Doesn’t sound like a hardware issue (faulty butttons/connections, pocket lint interference, etc.) if it works normally outside of Shuffle mode. One that could be fixed anyway. Certainly, it could be one of the millions of solder points or pathways on the circuit board that have failed, but try Miikerman’s suggestion of manually re-applying the firmware and see if that helps.
Otherwise, looks like it’s time for a new player. Be thankful it’s not a Cowon.
This is only an option but it would be worth the shot if you can do a factory reset. Just to isolate the issue.
This will do no good at all. A factory reset only resets your personal settings on the player, like Backlight Brightness, Backlight Time Off, Sleep Timer settings, FM Radio Presets, etc. It does nothing else.