iPod Nano 2G audio started skipping during music playback - what causes this?
I have encountered an issue similar to this on my iPhone, both on the 4S and 3GS. It took an embarrassingly long time to diagnose my headphones as the issue. I have a set of Sennheiser earphones with an inline remote, and if the jack becomes damaged, internal wires can get crossed and can start sending commands to the iPod application. I found that the play button would get hammered repeatedly as a result, and caused playback to stutter.

So, if your earphones have an inline remote and a damaged jack, try changing them. You might find a fix is cheaper than expected.