Last (?) Edit: The "problem" is solved: it was mainly a problem in the timing chain, due to a badly screwed optical fibre. A high level description of the problem is given here and a more detailed explanation of the investigation is here.
List of possible systematic biases
I thought it might be a good idea to list the possible systematic biases which could lead xkcd's character to win his bet. As many physicists (including, I guess, many people from the OPERA collaboration), I think it will end like the Pioneer anomaly. Of course, the current list only contains biases which are unlikely, but less unlikely than a causality violation.
Location errors and clocks drifts
The arXiv paper studied them, and seem to exclude it. The distance seems to be known within 20 cm and the synchronisation seems to be within 15 ns (6.9 statistical and 7.4 systematic). If this would however end up to be the explanation, it would be quite boring.
Update: Rumors seems to tell that the boring explanation is the good one.
Not the same neutrinos detected
The neutrinos are emitted on a 10.5 µs window, 175 times longer than the observed effect. It might be possible that the neutrino emitted early are not exactly the same as the one emitted late. Neutrino oscillation might, for example, then make early neutrino more detectable by the distant detector.
However, the detectors were built to measure the oscillation, so I guess that the OPERA collaboration thought about it, and rejected it for whatever reason. I suppose an explanation along these lines would mean interesting new particle physics.
Update: This possibility excluded by a new experiment with 3 ns pulses.
Errors in the statistical timing analysis
The timing itself is based on a quite elaborate statistical analysis. Furthermore, the pulses are quite long (10 μs), so an error in this analysis could easily be of the good order of magnitude.
Update: This possibility excluded by a new experiment with 3 ns pulses.
Jon Custer hinted at something, which I think is best explained via an analogy.
Imagine you can walk along a pavement at 4mph. When the pavement is empty, it takes you an hour to travel four miles. But when the pavement is crowded, you're dodging around people and bumping into them. You're still walking at 4mph, but it takes you an hour and a half to travel the four miles. And if you're a little old lady with short little steps walking at 4mph, you're held up more than if you're a big guy with long strides walking at 4mph. Now let's look at your questions again:
But I wonder why their speeds differ in any other medium?
Because the light interacts with the material, and those interactions are wavelength dependent.
And why Red light travels faster while it has less energy than blue light?
Because the light interacts with the material, and those interactions are wavelength dependent!
![enter image description here](https://i.stack.imgur.com/qQgkr.gif)
Best Answer
The answer is yes. Neutrinos will travel faster than light in a medium with a refractive index ($n$) greater than one (which is the case of air). Indeed the speed of light in that medium will be $v_{\text{medium}}=c/n$ where $c=2.998\times10^8$ m/s and $n>1$.
Then, because neutrinos interacts only very weakly (only through the weak nuclear force) with the medium, neutrinos will barely be slowed compared to how much light is slowed and thus will go faster than light. Remember that neutrinos are almost massless and thus already travel to nearly the speed of light.
--- New Edit --- Indeed, the neutrino speed will depend on it's energy (as pointed out in comments). But I think that in most process in which neutrinos are produced (take for instance a beta-decay), the energy of a neutrino is enough to consider it as going to nearly the vacuum speed of light. So strictly speaking, the answer is that it depends on the neutrino energy and what type of medium you are in.