How do you solve the “chicken-and-the-egg” problem?

Here are a couple ideas. I'm not sure about the specifics of what you're trying to do, so they may or may not be apt :)

1. Low risk buy-in for one party. Say you're doing a niche eBay site, find sellers who would be willing to post a few items on your site. They don't take much risk because it doesn't cost them much -- if no one buys anything the inventory isn't lost. You'll want to identify a few, "visionary" sellers (someone who is excited and is optimistic about where your site is going) who will be patient enough to be an early adopter.
2. Partner with an existing business. Say you're making a social network for book lovers, and you need to build your user base (ignore integrating with existing social network for this example). Find websites that you can add value to, like a book eCommerce website. You increase their value prop to users, they send you traffic.
3. Scaffold. Say you're building the next 99designs and you need designers and buyers. Hire some designers to fill the void in the short run to fulfill buyers, or alternately create some fake projects to encourage designers. This also works for content sites, like if you were making a YouTube specifically for cat videos. Create a bunch of content yourself to draw in traffic.

One idea may be to simulate one side of the transaction. A friend of mine sells fashion merchandise to large department stores. However, to get into these department stores the stores require merchants to participate in trunk shows first. A trunk show is a temporary display setup in stores to test to see how your product does in various locations. What my friend did was essentially paid people to go into the store to buy the product.

The 99designs idea is pretty much the same thing, just pay people to do one side of the transaction until it becomes self sustaining.

Just to add a few ideas that might apply in some cases:

1. Try not to inform either party about any statistics about the other party. I believe Apple uses this model on their Apps Store, as no statistics on the sales rates of individual apps are publicized. This means that developers could believe that it is very lucrative to develop apps, when it is not. This method is not ethical, but belongs to the theory around this.
2. Provide a benefit for those that come first. For the eBay case, this could be front page showing for a month for the first 30 products that get offered.
3. State your estimates about the future, meaning how many visitors, buyers you expect to get in the future.
4. For distributing Skype before network economics has started working, try doing it by invitation only, to make it seem exclusive.

By right there is no real definitive answer to the Chicken and Egg problem else the problem wouldn't exist would it? I hate the C & E issue because I have seen people argue and discuss the problem in circles without ever making a choice.

And that is my answer to the problem. Make a choice! To escape the endless cycle of blaming chickens and eggs, just pick one to make a meal out of. Come up with several viable options as Greg has and make a call.

In the case of attracting buyers and sellers, I would say target sellers first. You won't have an audience, but many sellers (especially small time ones) are always looking for new (mostly free) outlets to sell their goods and services. So you may have to offer free service to the first group of sellers until you start attracting a crowd. After you have a pool of sellers, start marketing to the buyers.