What the result means, essentially, is that in certain toy models there can be no algorithm deriving some macroscopic characteristics (spectral gap) from microscopic parameters of the models. The main import is that we get a Gödel sentence that unlike the original has some explicit mathematical meaning. Let's be generous and assume that the situation extends to more realistic theories of matter. What are the philosophical consequences for reductionism?
First, existence of undecidable sentences is a property of a theory, not a property of reality it describes, so we are talking not about ontological reductionism but about theory reductionism. Second, the authors mean "undecidable" in two different senses, one result states that there is no algorithm for finding the spectral gap in a class of models, the other result states that in some "artificial" models existence of the gap is neither provable nor disprovable. The former is not exactly surprising, deriving macroscopic properties of models is highly non-trivial even in classical statistical mechanics, although this may be the first explicit proof of it. The latter is more interesting, but undecidability is always relative. The Gödel sentence of arithmetic is provable in the standard set theory (ZFC), the Gödel sentence of ZFC is provable if one additionally assumes that there is an "inaccessible" cardinal, the continuum hypothesis is provable if one assumes that the sets are "constructible", and so on.
And in the end the difference between the two senses is technical, both mean that theoretical analysis of models requires non-trivial insights, whether using existing ways of reasoning non-trivially, or discovering new ones. But this has always been the case historically even in arithmetic, proofs of interesting number-theoretic results, even decidable ones, weren't found by an algorithm. Matiyasevich even proved in 1970s that there can be no algorithm for deciding solvability of Diophantine equations, it doesn't mean that specific Diophantine equations can not be solved or proved unsolvable. Wiles did the latter recently for Fermat equations, and we still don't know if arithmetic alone is sufficient for his proof. Cubitt, one of the authors, says as much: "It's possible for particular cases of a problem to be solvable even when the general problem is undecidable, so someone may yet win the coveted $1m prize".
Mathematicians have a notion of a "wild" classification problem, where classification of certain theoretical objects is intractable in principle. Classification problem for pairs of ordinary matrices is already wild, there is no surveying "Jordan canonical forms" for pairs. Cubitt implies that the source of undecidability in their case is another wild problem:"The reason this problem is impossible to solve in general is because models at this level exhibit extremely bizarre behavior, that essentially defeats any attempt to analyse them". So if theoretical reductionism was supposed to mean that one can get an algorithm for finding high level properties of derived objects from axioms for basic ones then reductionism was doomed for a while now. To summarize, there are no consequences for ontological reductionism, and for theoretical reductionism the paper confirms what we always suspected: reducing high level theory to a low level theory is a non-trivial business.
EDIT: I asked a question on Math Overflow about the technical side of the result. The paper was on arxiv for a year and is well understood by experts. The undecidability in it is typical, the proof is based on the undecidability of the halting problem for Turing machines, and is analogous to Matiyasevich's proof for Diophantine equations. This means that we are no more likely to encounter undecidable Hamiltonians in physics than we are to encounter Gödel sentences in number theory. In particular, the status of the spectral gap millenium problem for the Yang-Mills Hamiltonian is unaffected.
