Number 8 on the YCombinator's "Startup Ideas They Would Like to Fund" is dating:

Dating. Current dating sites are not the last word. Better ones will appear. But anyone who wants to start a dating startup has to answer two questions: in addition to the usual question about how you're going to approach dating differently, you have to answer the even more important question of how to overcome the huge chicken and egg problem every dating site faces. A site like Reddit is interesting when there are only 20 users. But no one wants to use a dating site with only 20 users—which of course becomes a self-perpetuating problem. So if you want to do a dating startup, don't focus on the novel take on dating that you're going to offer. That's the easy half. Focus on novel ways to get around the chicken and egg problem.

I wonder how this chicken and egg problem could be broken. Could it be by providing another value added service as a side product? Maybe you can help search music on the Internet and this could be used to build up a "profile" of people which might be able to bootstrap you. Or maybe one can use already established social space like Facebook, create an innovative Facebook dating app? Dating is always going to be attracting a lot of interest so it is a good idea to be thinking a solution.