After hearing (esp. from Morten) lots of good things about it (but not caring that much, because I don't pay for long-distance anyway when I call in the U.S. via my cell, and I don't call out of the country very often), I finally tried it recently to talk to a friend who's in Moscow right now. This is after I bought a phone card that let me call there for a few cents a minute. The voice quality on the Skype call was way better than the land line. Pretty impressive. Free and better is a strong sales pitch.
We still had a little trouble—the calls seemed to consistently lose quality after 7-8 minutes. A call-back would restore it. (I wondered if it was by design, as a temporary scaling tactic. I don't know if the calls are straight P2P or not. If so, that wouldn't really make sense. Maybe it was a fluke.)
However, like IM and other new technologies that are just subtly different than the old ones, where Skype probably gets interesting, is not just in replacing the old thing with something better and/or cheaper. (The experience is still weird compared to using a phone.) But in creating new behaviors that just weren't worth doing before. What will an instant, always-on, and good-enough quality voice connection integrated with your other information and communication tools do? I don't know. For virtual teams or people who work at home, quite a bit, I would imagine. For others, quite a bit on the social/entertainment side.
I wonder if Skype will open itself up as a platform. That could be hot. ("Click here to talk to me now.")