Cold Stone has done a great job at establishing their brand. While you may think it's "only okay ice cream", the general public likes to think it's a lot better because of how it's presented to them. If they didn't make it on the titular cold stone, and didn't have the toppings displayed in full before guests, it would be just like any other ice cream place and not had nearly the same success. That's essentially what TCBY before it was--a basic ice cream shop where you ordered, they scooped what you wanted out, and you were done. Cold Stone also has a bit more repeatability factor, IMO, in that you're actually encouraged to mix and match different flavors, most of which are pretty original (I think birthday cake is one, for instance).
I personally tend to avoid ice cream because it's sugary and bad for you, but I can see how Cold Stone has managed to generate hype. In a place where your only other option is soft-serve or Dip N Dots, it's a pretty big deal. Not to mention, while it may be ordinary on its own, it acts wonderfully as a complement to a fun vacation.