Having a problem with iPhone song playback

I'm having an issue with my iPhone which is really annoying. I just found out my roommate is having the same problem. Essentially, we're having issues playing back certain songs. For some reason, particularly with one album, songs will play for about 40 seconds and then stop and then it'll skip to the next track. It's really weird. I've tried a lot of different things. Removing it from the library, adding it back, re synching...nothing is really working. Any suggestions?