Interesting. Have you tried turning Shuffle on and then pressing down-down-down? Or turning off the "always randomize" check box on that root folder and re-synching?

If it still has trouble, perhaps there is an item somewhere deep in the tree that's causing problems. Would be interesting to find out which one. Get a serial log if you can.