Lionel's having the same problem that I am. It's the shuffle mode that can be turned off and on in the Controls menu (same as the second button from the right on the bottom).
I have found that with Shuffle on, it'll go eight or ten songs in a row, then skip to somewhere else in the playlist. Very aggravating, as, like Lionel, I use that mode a lot. (I have a smart playlist I call Daily Listen, which I like to turn on with Shuffle and I (USED TO) get a nice random mix of stuff.)
I called Apple Care, but we were unable to fix the problem.
I'm eagerly awaiting the fix for this...
CJ