I work with stellar models, so I thought I'd chip in here. My instant reaction is that you shouldn't worry too much: determining the age of a star is difficult and different models will disagree (sometimes significantly!) on that age.
How reliable is this research?
I can't see an obvious reason to doubt the conclusion.
What method do they use to measure the age of such a star as Methuselah?
Basically, one tries to measure as many properties about the star as accurately as possible, and then find the best fitting stellar model. These models are solutions to a set of differential equations (in time and one spatial dimension) that tries to capture all the relevant physics that determines how stars evolve. The bulk physics is a fairly well-defined problem but there are several potentially important components that are lacking in these models. (I'll expand on this if desired...)
The usual difficulty here is breaking down the degeneracy between brightness and distance. That is, a distant object is fainter, so it's hard to know whether a certain object is intrinsically faint or just further away. The principal result in this paper is the Hubble-based parallax measurement, which makes a big improvement on that distance measurement and, therefore, the brightness of the star. The other things they use are proxies for the surface composition and the effective temperature of the star, as far as I can see.
Incidentally, this is where I would suspect the tension can be resolved. If you look at Fig. 1 of the paper, they show the evolution of different stars for different compositions. What you're looking for, roughly speaking, is lines that go through the observed points. That figure shows that if the oxygen content is underestimated, then the best fit is actually about 13.3 Gyr, which is no longer at odds with the age of the Universe.
Take note of Table 1, where the sources of error (at 1$\sigma$) are listed. It's interesting that, not only is the star's oxygen content the largest source of error, but even the uncertainty of the oxygen content of the Sun is a contributor!
Which is more likely to be wrong, the age of Methuselah or the current estimate of the age of the universe?
The age of Methuselah, definitely. I would describe our estimates of the age of the Universe as in some way "converegent": different methods point to consistent numbers. Sure, Planck shifted the goalpost by 80 Myr or so, but it'd be a real shock to see that number change by, say, half a billion years.
Could relativistic effects account for some of the age?
I have no idea and haven't really thought about it. Since I'm pretty sure this isn't a big problem, I don't think relativistic effects are necessary to explain the discrepancy.