Why error rate converges faster if the visiting order of mini-batches are changed at each epoch? I'm quoting from the paper:

As for any stochastic gradient descent method (including
  the mini-batch case), it is important for efficiency
  of the estimator that each example or minibatch
  be sampled approximately independently. Because
  random access to memory (or even worse, to
  disk) is expensive, a good approximation, called incremental
  gradient (Bertsekas, 2010), is to visit the
  examples (or mini-batches) in a fixed order corresponding
  to their order in memory or disk (repeating
  the examples in the same order on a second epoch, if
  we are not in the pure online case where each example
  is visited only once). In this context, it is safer if
  the examples or mini-batches are first put in a random
  order (to make sure this is the case, it could
  be useful to first shuffle the examples). Faster convergence
  has been observed if the order in which the
  mini-batches are visited is changed for each epoch,
  which can be reasonably efficient if the training set
  holds in computer memory.

I'm looking for intuition behind the statement (embolden) above.
 A: Claim 1. When dealing with prediction, averaging different models having the same performance (in terms of your error function) improves the performance. This is due to the convexity of your loss function. As an aside, the less correlated your models are, the better is the gain you achieve averaging them.
When you train a batch model, the order of the lines does not matter. In a streaming algorithm, the order of the lines matters. Shuffling the lines and training the model on the different versions of the file will produce different results. As the model have the same parameters, they usually have comparable performance. As they are different (slightly), their average is usually better than every single algorithm.
More details about this fact can be found in the chapter 5 of "Online Learning and Online
Convex Optimization", by Shai Shalev-Shwartz.
Visiting the batches in a random order somehow accomplishes the same process: it produces different weights that are averaged on every epoch.
A related question is this one : RANDOM learning rate in gradient descent. Authors claimed that multiple training epochs performed on the same data set with a randomized learning rate achieves better performance than a deterministic learning rate.
