In a narrow sense, the Coase Theorem is correct. If the parties are bargaining about a single, static externality, the outcome will be "efficient" regardless of initial property rights (assuming that we exclude distributive concerns from our definition of efficiency). But this completely ignores the impact on incentives to create an externality.
Suppose that we inhabited a world where farmers had no property rights against encroachment by cattle. In this world, the first thing I'd do is start a company (preferably with an nefarious-sounding name like Multinational United) that raised cattle specially bred to ravage cropland. I would locate these cattle near a large number of farmers and announce that each they had to pay me $100,000 to avoid being overrun by the herd. For most farmers, this would be worthwhile, and I'd make a bundle of money.
Of course, this would be inefficient: if any farmers didn't find it worthwhile to pay the $100,000, their farms would be destroyed. And even if we assumed that evil Matt had perfect information and could charge a special rate to each farmer to make sure that it was worthwhile for everyone to pay, this would be inefficient in a different way. Payments that varied according to ability to pay would effectively be a tax on productive assets, which in the long run would discourage the accumulation of those assets.
After I set up a lucrative business exploiting farmers, I would retire by moving into dense residential neighborhoods, buying houses, and blaring extremely loud music at different corners of each house until I was paid compensation by the nearest homeowner. Again, this would be monstrously inefficient. If I committed to charging $50,000 a year to everyone, some people might not be able to pay, and would be forced to suffer the hearing damage and general psychological trauma that comes from listening to my music. If I charged different rates according to accumulated wealth and income (making it so that everyone could pay), I'd be creating a large implicit tax on wealth and income. Either way, this is far from the efficient utopia envisioned by Coase—and it can all happen in a world without transaction costs!
If there was ever a case where you had to wonder whether some economists were actually confused impostors from the planet WZ-15, this would be it...