This problem falls under the classification of "critical mass" problems. I think any solution that works for one of these types of problems, is likely to work for the others. "Critical mass" is when the problem is not in coming up with a good alternative, the problem is that having a critical mass of users for your solution is going to be an important part of the value you offer to your customers.
I've never been able to flesh this out enough to the point where I was sure I had a solution that would definitely work. But here's what I came up with so far: make a website, and a company, whose focus is solely on building critical masses of users for those "new alternatives". It would consist entirely of methods and social software that could be used to build critical mass.
For example, users could state how many other users would need to be using a new service, before they would try it. Or how many of their friends were doing it. Then, you inform them when those numbers are reached- when the 100th user is there, the 1000th user, etc. (whatever they named), the third user after they posted, etc. Ideally, you would have enough people who've registered their herd-desire, that you could set off a chain reaction from 0 to the number needed for viability.
Unfortunately, that probably wouldn't work for anything but what attracts the most savvy users. I think you might have to pay people to form flash mobs. I.e. people go hang out on the website, and they get a notice of "if you're interested, go to this dating site and fill out a profile, and earn $5. Each other new user you find earns $1 for you". Especially the more social it is, the more it would work to have a flash mob thing going on, where there's only one opportunity at a time. Then you hope that a temporary critical mass sustains itself- that if it's good enough, people will stick around and the rest of the nuclear reaction can complete itself.
To some extent, what I'm proposing is the Mechanical Turk thing Amazon does, but for user bases. And you'd probably have to do a lot of user verification.