In a very strict and narrow view, the narrow pipe criticism is a valid attack, in that it shows that a hash function with a 256-bit output size and a "narrow pipe" (running state no larger than the output) offers, at most, the preimage resistance that could be achieved with a hash function with an output of 255.34 bits. On a more practical point of view, this has no consequence whatsoever on actual security. Gligoroski offered this paper as an argument for wide-pipe designs, in particular his own proposal for SHA-3, called Blue Midnight Wish.
Aumasson, one of the designers of BLAKE, another SHA-3 candidate (a narrow-pipe design), said that this attack was of the kind "my-pipe-is-bigger-than-yours" and was not very serious. It is however quite telling that among all the research result on the 14 second-round SHA-3 candidates, the narrow pipe criticism by Gligoroski is probably the best known attack -- which means that all 14 functions are, as far as we know, quite robust. One can also note that for the 3rd round of the SHA-3 competition, BLAKE was selected, but not BMW.
MD4, MD5, SHA-1, SHA-256 and SHA-512 are narrow-pipe designs and nobody misses a heartbeat on that fact.
The reason this attack works (for very low values of works) is that a random function is not likely to have a 1 -> 1 mapping of inputs to outputs if it's a truly random function. In fact, the way the math works out, a perfect random mapping would only produce 1 - 1/e of the possible output space. This works out to 0.632 or so, and since a little less than half the outputs won't happen, reduces the difficulty of finding a pre-image by a partial bit (a full bit would be if half the outputs wouldn't happen).
As you can see, this is purely theoretical and frankly rather silly.