Camanho, Edelstein, Maldacena and Zhiboedov have shown that gravitons can experience a negative Shapiro time delay, i.e. a time advance, in Einstein-Gauss-Bonnet theory. They studied gravitons propagating in singular "shock-wave" geometries. We study this effect for gravitons propagating in smooth black hole spacetimes. For a small enough black hole, we find that gravitons of appropriate polarisation, and small impact parameter, can experience time advance. Such gravitons can also exhibit a deflection angle less than $\pi$, characteristic of a repulsive short-distance gravitational interaction. We discuss problems with the suggestion that the time advance can be used to build a "time machine". In particular, we argue that a small black hole cannot be boosted to a speed arbitrarily close to the speed of light, as would be required in such a construction.