tl;dr: Light and gravity both move at "c" locally and near us under this proposal, so we would notice no difference from General Relativity (GR) or local tests of Special Relativity. In fact, it's only the generality of GR that lets one call this a variable speed of light (VSL) theory rather than a time-varying speed of gravitational wave theory (see my last paragraph before the footnote below). The relevant time is confined to the very early universe.

Afshordi and Magueijo's argument is essentially a bimetric theory of gravity.

In General Relativity, there is a single metric and universal coupling of all matter, radiation, and gravitons (more on those in four paragraphs) to it. There is a tangent space (illustration at [0]) at each point in spacetime, and the Minkowski metric is induced on each of them, which is how we get Special Relativity locally. In the absence of any matter, radiation or gravitons, all tangent spaces are aligned with one another, and they all have universal extent; we call that Minkowski spacetime. Once you add in matter, radiation or gravitons, the tangent spaces contract and become unaligned, and you can no longer use the Minkowski metric to describe things outside a chosen tangent space -- another metric applies instead, and all matter, radiation and energy couple universally to that.

The crucial point though is that there is one metric, and the change of vector magnitude and direction from point to point in spacetime is described by it and applies to everything in the spacetime.

In a bimetric theory some matter, radiation or gravitons couple to one metric, and some to the other. In the authors' argument, gravitons couple to the second metric while everything else couples to the first. Moreover, the graviton metric only applies in the very very early universe and quickly decays into indistinguishability from the matter-energy metric. So General Relativity still applies everywhere that our tests suggest it's correct.

Bimetric theories have been studied since Rosen (of Einstein-Rosen bridges) proposed the idea in 1940, but they are pretty strongly disfavoured by evidence supporting the single metric of GR, most recently by the LIGO observations. Consequently most viable bimetric theories have the second metric operate in inaccessible regions like the very early universe. Afshordi & Magueijo's metric decays so early as to produce almost no observables at all, but atypically for modern proponents of bimetric theories, they deliberately predict some observables in the relic fields like the cosmic microwave background.

Crucially, the second metric in Afshordi & Magueijo's approach applies to gravitons only.

Gravitons are a feature of canonical general relativity and other perturbative approaches. Such approaches are perfectly fine except very close to physical singularities where (on a Feynman diagram) multiple loops of gravitons start appearing. In other words, you can quantize General Relativity's clasical spin 2 symmetry gravitational waves in an effective field theory (in the Ken Wilson sense), and in so doing reproduce General Relativity's results exactly as long as you aren't in strong gravity.

Strong gravity is not a consideration in A & M's proposal. However, unlike canonical general relativity's massless graviton, theirs has a mass in the early universe which decays to zero in the later universe.

In their proposal, in the very early universe, the tangent spaces at each point on a photon's worldline are different from those on a graviton's worldline. This means that for a graviton and a photon at the same point in spacetime, the magnitude and direction of the vectors in the tangent spaces differ, and pretty wildly. The "next step" for the massless photon can have a much (much, much) longer spacelike component than the massive graviton; the photon can exit the graviton's causal cone (however the mass of the graviton is still small enough that massive matter particles still stay within the graviton's causal cone). Thus photons can take energy out of a hot clump of collapsing hot dense matter to a clump of cooler collapsing hot dense matter without altering the collapses. With a massless graviton, the very hot clump cooling radiatively (emitting photons) would let it collapse while the cool clump undergoing radiative heating (absorbing photons) would impede its collapse.

A & M thus have a mechanism for evening out the temperature of the early universe, in a way we would expect to see reflected in the relic fields (notably the cosmic microwave background, which our current technology lets us see a lot more clearly than e.g. the cosmic neutrino background).

As their metric decays early in the universe's history, they can preserve star-nebula thermodynamics and other observables in the present universe.

By having their second metric decay early enough in the universe's history, they can preserve the Standard Model in the later universe, and can try to sweep some of the gauge invariance consequences under the carpet as marginal-to-irrelevant.

It's common to call this kind of bimetric massive-graviton approach a variable speed of light approach, although that betrays the critical point, namely that there's a variable speed of gravity. Gluons, being massless, have the same causal cone as light when their second metric is operating, but gluons are ignored because they are generally not seen due to confinement by the strong nuclear force. Everything else including neutrinos stay within the graviton's causal cone rather than light's, and because of the importance of gravity in the hot dense phase of the early universe, that lets one treat light as being "faster", effectively, in that phase than in the later universe. In order to deal with the causality problems this exposes, a fast phase transition is introduced, with all massless particles adopting the same speed suddenly.

A & M's approach instead introduces a extra time-like dimension, which is an idea from M-theory that raises a serious problem: that dimension introduces new degrees of freedom which we simply do not see objects in the modern universe taking, and which will also tend to mess up the Standard Model and structure formation. They say just after their equation (12), don't worry, we can solve that with a zoo of particles so heavy that we cannot even think of seeing them at LHCb energy levels, and which hide the graviton's mass everywhere that General Relativity as an effective field theory is valid.

The motivation for A & M's approach is to avoid having to detail an inflaton field and its early universe symmetry breaking. Inflatons are similarly unlikely to be seen at LHCb, which is a minus, but they can follow the sort of symmetry breaking we see in the electroweak phase transition, while the bimetric massive gravitons do something different. Additionally, Cosmic Inflation certainly does not have more free parameters than A & M's approach, so it is not very satisfying if there is no way to distinguish between them. (In fact, Magueijo has said he expects that their approach will be precluded by forthcoming detailed studies of the cosmic microwave background, and he is probably right that the book will be closed on bimetric massive gravity in the early universe if that is the case.)

Maybe the bigger problem that they say they will address in a paper currently in preparation (their endnote [24]) is that their high-energy completion is sensible only in flat spacetime. That's relevant because they need that high energy completion to make their "don't worry" argument plausible; and because Cosmic Inflation (and more generally Big Bang) embraces enormous spacetime curvature in the early universe. This is fairly easy to think about: we have enormous spacetime curvature thanks to the metric expansion of space -- intervals between the centres of galaxies increase further from the hot dense phase of the universe both in the concordance cosmology and in A & M's. Under time-reversal, these intervals vanish close to the hot dense phase of the universe (and indeed, so do galaxies, which "un-form for the last time"). The collapse under time-reversal of the universe breaking down into flat spacetime will take quite a feat to explain.

And it's important, since they essentially require that all the tangent spaces of all the particles in their bimetric phase are perfectly aligned, and that can only happen in flat spacetime. (The critical feature of flat spacetime is that the Minkowski metric is induced on all the tangent spaces of all the matter, radiation, and gravitons in the universe; variable-speed-of-light comes from analysis of this under the Poincaré group, which is the isometry group of flat spacetime and which has "c" as the sole free parameter. Locally the way you deal with Poincaré invariance in a bimetric theory is to have a location-dependent value of c and ignore the underlying reality of unaligned tangent spaces. But that is hard to extend outside of regions of spacetime where the volumes are not exactly zero, or at least very close to zero.)

[0] 2d-tangent space of a point on a sphere: https://en.wikipedia.org/wiki/File:Image_Tangent-plane.svg
The tangent spaces of points on the sphere infinitesimally close to the blue point are very closely aligned with the tangent space on the blue dot. But the tangent spaces noticeably disalign at points on the sphere at greater distances from the blue dot. Also relevantly, all points in the depicted 2-d tangent space themselves have a tangent space that is perfectly aligned with the one on the blue dot.

In our 3+1 universe, we concern ourself with 3+1-d tangent spaces on all points in the spacetime. At each point in a tangent space, Special Relativity applies; in tangent spaces that are not perfectly aligned, SR does not. Spacetime curvature causes non-aligned tangent spaces to appear, just as the curvature of the sphere in the diagram causes non-alignment of tangent spaces on points on the sphere.