I seem to remember reading that this issue was connected with the slow (Class 2) sdcard we have as stock. I searched and found a few posters that claimed the issue only went away after they switched to a faster sdcard. One guy swore that his phone was cured by switching to a class 6 card.
They also claimed that the issue was with the recording of the videos and was not a function of playback. You could test this out by putting one your videos on your pc and see if the skips are there too when played.