I never understood why people would dislike cilantro until I moved from southern California to Chicago, where produce is imported over mind-boggling distances a large fraction of the year. I discovered that it is absolutely vital that cilantro be fresh, sold and used soon after harvesting. This seems to be a matter of both flavor and simple mechanics. As an herb, the fragrance of fresh cilantro fades relatively quickly -- it is not durable like curly parsley. More mundanely, cilantro's large surface area and small volume means it dehydrates very rapidly. Thus, by the time cilantro reaches my kitchen in the Chicago winter, it has morphed from a crisp brightly fragrant herb to something akin to flavorless pieces of rubber laced with fiber.
On a more practial note, cilantro is best stored washed and cleaned, in a sealed tupperware-type container lined with paper towels.