Does that mean Hawking radiation [1] doesn't exist? Matter, anti-matter pairs being created on opposite sides of the event horizon of a black hole and thus not being able to pop out of existence.
No, Hawking radiation is based on well-known physics (virtual pair particle-anti-particle creation) which arises near an horizon (which you can treat classically: the so-called quantum foam play no role).
Simplified, hand-waving explanation: virtual pair creation can occur in any quantum field theory. We have quantum field theory describing three of the fundamental forces (strong, weak, electromagnetism ... ok, two forces as the last two are unified as electroweak). Pair creation can occur at a (length) scale that is much larger than the Planck scale. (the energies involved are much lower than that of the Planck scale). Treating a black hole classically, one particle from a virtual pair can cross the horizon and the other escape at infinity - thus you get Hawking radiation. At those scales, the event horizon would appear to be smooth - like a pure 2-d surface.
However, for gravity, we do not have an experimentally verified quantum theory. It is thought that such a theory would contain the equivalent of virtual pair creation, namely fluctuations in the space-time. So, at the Planck scale, one would expect that space-time would not be smooth and thta you would have spontaneous appearance of quantum fluctuations that would give your space-time a foamy structure. However, these structures would be incredibly tiny and, for "macroscopic objects like a proton (!)", the space-time would still look smooth; fluctuations of the even horizon of a black hole would occur at much smaller distance than those involved in virtual pair creation.
The article is a bit dodgy in this regard. It just means that at a quantum level, the energy fluctuations (as observed in this experiment) are not big enough to cause significant space-time alterations.
So, it is foamy, but not as foamy as other people thought (the idea of virtual particles having no gravitational contribution sits uncomfortably in my mind).
The average would be unchanged, but the whole point of their measurement is to measure the resulting statistical broadening of the event.
That is, if the burst lasted 1 second (I made this number up!), you'd expect all photons to arrive within 1 second of each other. But if space-time foam had a strong effect, you would expect the same average time, but you might expect the spread of the data to be larger: maybe 5 seconds (also made up). (Essentially, randomness like this would be expected to increase the standard deviation of the arrival times.)
So by measuring the spread of the photon arrival times, you can put an upper bound on how big the space-time foam effects can be: the actual spread is (very roughly) the sum of the actual length of the event plus the spreading due to space-time foam. These folks are claiming that for certain models of space-time foam, the photons they observed arrived too close together to be consistent with the existence of that foam at the expected scale (assuming it's not a statistical fluke).
If the situation was chaotic (which I would presume a system with many random perturbations to be) the expectation is for the repeated small changes to have a significant impact.
My guess would be this would be true only if they were coherent, and the resonant frequency were some multiple of the Planck length. The many small random perturbations would largely cancel each other out and the remainder would be insignificant (not energetic enough) to meet the lowest energy requirements to nudge a photon by even a miniscule amount.
[1] http://en.wikipedia.org/wiki/Hawking_radiation