There's always Facebook and LinkedIn. I suspect Diaspora users will just use those like address books, at least at first. Even if Diaspora never supplants Facebook, it will be a good thing as an alternative.
We have real life contacts, don't forget that. That will help a lot.
Real world contact helps the problem, but it doesn't solve the problem.
Fairly certain google would make it fairly easy, if Diaspora ever takes off.