What to do when untrusted claims are made in an extended abstract of which the full version hasn't appeared
The obvious place to look for either a substantiation or a retraction of the extended abstract's claim wold be on the arXiv. Also, since the author is still active, you or your adviser could write to him and ask about the algorithm and its running time.  If you still can't get the information you need, then I think you can publish your work and include, in a "Related Work" section of your paper, a citation of the extended abstract and a statement to the effect that you have been unable to find the details in the literature or to reproduce them yourself.  Of course, if you manage to contradict the claim in the extended abstract (or to show that it would imply implausible things like P=NP), then you should say that.