There is one possible mechanism by which the speed of light may have changed. If there are large (order 1 mm) extra dimensions, some models predict that the compactification scale (the radius of curvature for the extra dimensions) will "relax" slightly over time after the universe forms. A tiny change in the speed of light may be a signature of that relaxation. If this is the case, relativity is unmolested. What we are seeing is the principle of relativity applied to a universe whose geometric structure is changing slightly over time. Ouch! Can we have an ice pack over here? I think I sprained something trying to wrap my brain around this.
Did you say that if the shape of the universe is changing it could effect the speed of light?
a.cricket