This issue has happened to me before, with certain songs (specifically, anything by Vampire Weekend, good thing I don't like them much). It would be fixed by a reset. But it doesn't seem to happen as often as you make yours sound. I would suggest you register your serial number (on the back of the device) on Zune.net support and see what your warranty status is before giving up. If someone has already registered that number, I'm not sure what you can do, but you may be able to sort that out with Support as well.
- Grant F