I agree with the Major cities approach. You need to think about cities where a lot of people visit/move to and want to meet new people. The market is certainly there, as my girlfriend and I use meetup.com for exactly this reason in Tokyo.

Sidenote: I wanted try the app out but couldn't find it in the Australian or Japanese stores. Have you limited it to US only? If so that seems crazy to me. So what if there are no other users in the area?, improve the feedback/take that opportunity to get them to spread the word.