Twitter had that chicken-and-egg problem too, but do you know how we solved it? We all joined Twitter and then told people we wanted to follow that we were there.
With the difference, that back then Twitter didn't exist. Only in form of IRC or such and Twitter could distinguish from that. A new service has to be unique in a new way.
