A paper which makes strong claims ought to be sufficiently clearly written for readers to check those claims. I don't find the current (http://arxiv.org/pdf/1211.3405v2.pdf) version of this paper expresses its results clearly enough to make a concrete assessment.
But if it were, I'd want to check:
a) whether the quantum part of the algorithm solely consists of Pauli measurements on a cluster state.
Such a measurement-based quantum computation can be simulated using polytime classical processing (due to the Gottesman-Knill theorem), and hence one would have a solely classical superfast search algorithm.
b) whether the oracle used might be of a different type to the oracle in Grover's algorithm.
The oracle in Grover's algorithm has the property that it must recognise the target string, but, crucially, it does not need to know this string in advance, or be able to calculate that target string in polytime (see Nielsen and Chuang chapter 6 for a discussion of this).
Unless P=NP, an oracle which knows the target string needs to be more powerful than one which merely recognises it (consider a search for a solution of an NP-hard problem). I'd want to check whether the oracle here is of the "recognising" or "knowing" kind. If it is the second, then the extra computational power in the oracle might, on its own, explain any exponential improvement reported.