Well, my first guess is that if somehow you're blasting the iPod to full volume (and I wouldn't assume this to be true or you'd go deaf quickly), then it could clip the signal and sound like you're describing.
BUT, if it's just at normal listening levels, and you're *sure* it's not just through one single pair or headphones, then I'd say there's a problem. Either a connection issue w/ the headphone jack or an internal software issue w/ the software the iPod utilizes to playback the mp3's stored on it. You may wanna go to an Apple retail store if you have one near, or if not, give Apple a call and see if you can send it in for a replacement.
Good luck man, and make sure it's not the headphones, and for opinions sake, maybe let a few others listen to it and see if they hear the same thing.