Is Einstein's theory really challenged by the recent paper in news? A recent paper authored by Niayesh Afshordi and Joao Magueijo is in the news claiming to challenge Einstein's theory on constancy of light speed. It says light might have travelled with a faster pace during the initial stages of Big bang which apparently sets aside the inflation hypothesis. 
My question is whether it actually invalidates Einstein's relativity - which depends on constancy of speed of light. Or is it only applicable to the very early universe?
 A: Magueijo came up with the variable speed of light idea nearly twenty years ago. The motivation was as a way of explaining the homogeneity of the universe. At that time inflation was still somewhat controversial (perhaps it still is) and Magueijo's theory was mainly intended as an alternative to inflation.
Since then inflation has become more accepted and VSL theories generally became less popular. However there are beginning to be mutterings that inflation is such a vague theory that it's impossible to experimentally prove. That is, the theory has so many adjustable parameters it's hard to see what experimental data would conclusively rule it out. It is in this context that VSL theories are attracting more attention again.
But it must be emphasised that there is no experimental evidence that conclusively rules out or rules in either inflation or VSL theories. They both remain ideas that explain some features in an appealing way, but neither is more than an appealing idea right now.
As for the conflict with general relativity, both theories are concerned with the very earliest moments after the Big Bang, and I suspect most physicists already doubt that GR will hold right back to the Big Bang itself. We expect some quantum gravity to become important at very early times. So I'm not sure I'd say VSL thories challenge GR.
The new element in Magueijo's paper is a firm prediction about the effect of VSL on the cosmic microwave background. While the current measurements of the CMB aren't precise enough to test Magueijo's predicitions the next generation of measurements may be. However even if the measurements match Magueijo's prediction that will show only that his VSL theory is possible not that it's true. His predicted value for the spectral index would still also be compatible with a range of inflationary theories.
A: Einstein's 1905 constant-speed-of-light postulate is false indeed but Magueijo's claim that the speed of light was faster in the past has nothing to do with it. Einstein's postulate asserts that the speed of light is the same for any observer, stationary or moving - an assertion that is easy to disprove, in the following way: 
The initially stationary observer (receiver) starts moving towards the light source with speed v: 
http://www.einstein-online.info/images/spotlights/doppler/doppler_static.gif (stationary observer) 
http://www.einstein-online.info/images/spotlights/doppler/doppler_detector_blue.gif (moving observer) 
Two hypotheses are conceivable: 
Hypothesis 1 (Newton's emission theory): The speed of the light relative to the observer shifts from c to c'=c+v. 
Hypothesis 2 (Einstein's relativity): The speed of the light relative to the observer does not shift (c'=c). 
In order to test the two hypotheses, the observer measures the frequency - it shifts from f to 
f' = c'/λ = (c+v)/λ = f(1+v/c) : 
Quote: "Moving Observer. Now suppose the source is fixed but the observer is moving towards the source, with speed v. In time t, ct/λ waves pass a fixed point. A moving point adds another vt/λ. So f'=(c+v)/λ." 
Quote: "Now let's see what this does to the frequency of the light. We know that even without special relativity, observers moving at different velocities measure different frequencies. (This is the reason the pitch of an ambulance changes as it passes you it doesn't change if you're on the ambulance). This is called the Doppler shift, and for small relative velocity v it is easy to show that the frequency shifts from f to f(1+v/c) (it goes up heading toward you, down away from you). There are relativistic corrections, but these are negligible here." 
Clearly, measurements of the Doppler effect confirm Hypothesis 1 and refute Hypothesis 2. Einstein's relativity is based on a false postulate and will have to be discarded altogether.
A: 
Is Einstein's theory really challenged by the recent paper in news?

No. Because Einstein's theory is a VSL theory. See the Einstein digital papers. Einstein wrote this in 1920, note the second paragraph:

He said the curvature of light rays can only occur in spaces where the speed of light is spatially variable. Also see the Shapiro delay where you can read that according to the general theory, the speed of a light wave depends on the strength of the gravitational potential along its path. Anybody who tells you the speed of light doesn't vary is telling you about "modern" GR which isn't in line with Einstein's GR. They might insist it is, but it isn't. 

A recent paper authored by Niayesh Afshordi and Joao Magueijo is in the news claiming to challenge Eintein's theory on contancy of light speed. It says light might have travelled with a faster pace during the initial stages of Big bang 

I fear they've got this wrong. Light goes slower when it's lower. Because the energy density is higher. So light in the early universe should have gone slower too. If they say it went faster, then IMHO they're misunderstanding Einstein's theory rather than challenging it. 

which apparently sets aside the inflation hypothesis. 

Inflation is under some pressure these days. See Physicist Slams Cosmic Theory He Helped Conceive where Paul Steinhardt is rather critical. Personally I rather think that when you understand GR correctly, you just don't need inflation - it's a solution to a problem that doesn't exist.

My question is whether it actually invalidates Einstein's relativity which depends on constancy of speed of light. 

No it doesn't, because Einstein's relativity doesn't depend on the constancy of the speed of light. Another article worth reading is Is The Speed of Light Everywhere the Same? by Don Koks on the "Baez" PhysicsFAQ website. The answer is no. 

Or is it only applicable to the very early universe?

I know of no reason why it should be. 
