I have a yp-mt6. I've never noticed this problem, and I'm very happy with it. I think your problem may be the a/b button on top of the player. If you press the button twice, it will repeat whatever songs came between the two presses until you press it a third time. If you haven't been switching the hold button on the player this may be your problem.
Also, if you have a folder selected when you press play it will only shuffle music in that folder, though if you play just a song it will shuffle everything normally.
I got this mp3 player for running and excersising, i keep all my music in shuffle but the samsung when in shuffle plays songs twice ocasionally, for example when only one is done, than it plays another song than it plays only one again.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic