The shuffle setting is essentially random, which does _not_ mean that you won't hear the same song again until all other songs play. You might even hear the same song twice in a row, I suppose.
Are you hearing the same group of songs, and your other songs _never_ play?
If you scroll manually to a song that you haven't heard, and start play from there, does it revert to that same group songs, or play on to others?
All else failing, have you tried to restore your iPod?
Have you tried changing the playback settings in your iTunes preferences? You should be able to adjust the setting to make it _less_ likely for songs to repeat. I don't know how that would transfer to the iPod.
