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.
Many of the strongest spectral lines (e.g. Balmer absorption lines and resonance lines of metals) are very sensitive to the surface gravity of the star. This enables a distinction between main sequence dwarfs and giants because a giant star's surface gravity is factors of $\sim 100$ lower than that of a dwarf star of the same temperature and has narrower absorption lines. Conversely, white dwarfs have much broader lines, because their surface gravities are $\sim 10^4$ times larger than a main sequence star.
The reason that surface gravity plays a role is via hydrostatic equilibrium; the densities and pressures in a giant star's atmosphere are much lower at a given temperature. If an atom or ion suffers frequent collisions in a high density environment then the absorption cross section can be smeared out by "pressure broadening" - a catch-all term, which can refer to a number of mechanisms (Stark effect, van der Waals broadening, collisional broadening), whereby interactions can either perturb the energy levels of atoms and ions or truncate the radiative emission processes (e.g. Foley 1946; Griem 1976).
In main sequence dwarfs, pressure broadening is sufficient to give an appreciable cross section in the line wings and means that the visible lines are formed at a greater range of temperatures than would otherwise be the case. In giant stars, this broadening mechanism is ineffective, even in strong lines, and they are completely dominated by thermal doppler broadening close to the temperature where the line core is formed and this produces a narrower profile overall.
Best Answer
As John Rennie correctly says. Tc is formed by neutron capture in the s-process along with many other heavy chemical elements (Ba, Sr, Eu, Pb etc.). The conditions for the s-process require a neutron source. This is provided by alpha capture onto carbon 13, or sometimes neon 22 in more massive stars.
A plentiful supply of carbon 13 only exists (at the right sort of temperatures and densities, and there are other requirements too) inside asymptotic giant branch stars with helium and hydrogen burning shells. The AGB phase occurs near the end of the life (they end up producing white dwarfs) of most stars of less than about 8 solar masses.
The neutrons are captured in a chain of reactions by pre-existing iron-peak nuclei in the star to make the s-process elements. However, to be visible in the photosphere there also needs to be the right conditions to dredge up material to the surface.
The models of these events are complicated. The details depend exactly on the evolutionary stage, the overall metallicity of the star and more. This is thought to be why Tc is only seen in some AGB stars. More details as and when I find them...
Ah, but the other crucial point is the half life is short, so even when manufactured in AGB stars, it is not "passed on" to the next generation of stars - so it is not generally observed in most stellar spectra.