Harford does not necessarily show that the Fulton Fish Market fails. To an economist a "market failure" occurs when a given market does operate efficiently. It is possible to conclude from Harford's brief summary that the merchant's differential charges violate efficiency, but this is not necessarily true. What Hartford is really talking about is price discrimination-charging different prices for the same good. Standard economic models predict that competitive markets will not permit price discrimination since each transaction will occur (roughly) at equilibrium-if you're in a competitive market you can't distinguish between buyers.
Not having investigated the example cited here I can't say for sure what the conclusions are as to why price discrimination appears to occur. Often, though, what looks like discrimination is really just a given seller providing two different but similar-seeming goods. To give a poor example, imagine a soda machine in the lobby of a fast food restaurant. You can buy a 20oz soda from the machine for a dollar or buy a 20oz soda from the counter for eighty cents. If both are owned and provided by the restaurant, this would seem to be price discrimination-charging different prices (to different buyers) for the same good. But is the good provided the same? If the average wait in front of the machine is thirty seconds while the average wait for the counter is two minutes, the goods provided are really "20 oz of soda in 30 seconds" and "20 oz of soda in 2 minutes," and standard theory has no problem with different prices being charged. There may be some value in having a screw-top lid and not having ice in a paper cup, etc., and these seemingly small differences can mean that we're talking about two different goods. (Some theorists might consider such a case a monopoly anyway, since the good "soda in the restaraunt" is only provided by one seller-you wouldn't necessarily expect efficiency in such a case, whereas in the Fulton Fish Market a buyer could easily go to another vendor. If I remember correctly Steven Landsburg discusses movie popcorn in his book The Armchair Economist in similar terms.) In the case of the fish market, the actual cuts of fish might be subtly different, or have differing levels of freshness (though I'm sure a good economist will control for these factors). Pre-existing relationships with buyers may also influence price-setting, and the influence of transaction costs associated with search and bargaining will certainly play a role.
Much of macro-level standard econ. theory tries to minimize the problems that transaction costs present (in complicating the model tremendously) by assuming them away-buyers and sellers are assumed to be homogeneous, information is cost-free, prices adjust immediately and so on. The fact that these assumptions do not hold in micro-level transactions where information is costly, individual economic agents have unique properties, and market changes are not immediate should not be surprising. The standard model assumes that a sale occurs at equilibrium and that sellers do not have the power to charge a different price to some buyers, no matter how much they might want to. The empirical case of the Fulton Fish Market seems to violate this prediction. As I read him Harford says that this violation implies that perfect competition may not exist, not that "market fundamentalists" have designed a faulty system. In short, what is described is not necessarily a bad market, but instead an interesting case ripe for examination as to why (and whether) an empirical situation differs from theoretical predictions.
[Additionally, to your comment-market failures do not require irrationality. A true monopolist is being fully rational in price-discriminating, the point is that efficiency is not realized in that case. As to the question of different prices for the same good, I think Prof. Landsburg had an article on Slate a while back about tomatoes where he looked at similar issues.]