I skimmed(!) the paper, although it is really not my field, I am not sure it is asking the right question.
I went to the D-wave talk at SC'13 and spoke to the presenter.
We define speedup as T(classically)/T(quantum) for problems that can be solved classically , I sort of think we are missing the point unless we realises that T(quantum) is not an equivalent quantity.
For the readers, at SC'13 the D-wave talk focussed on using the D-wave machine as part of a feedback cycle to inform classical calculations.
I am just saying, with so few of these machines in circulation (although they are soliciting ideas , I've not heard back yet...), we might have to wait for the methods that show the real utility.
I agree though, the agressive PR is annoying.
A cryogenist friend of mine commented "It is a research project to get 20mK, not sure about the computing..."