I've thought about this a lot. Currently, my preferred solution to the problem of Sybil attacks in decentralized social networks is a reputation system based on a meritocratic web of trust.
Basically it would work something like this: By default, clients hide content (comments, submissions, votes, etc) created by new identities, treating it as untrusted (possible spam/abusive/malicious content) unless another identity with a good reputation vouches for it. (Either by vouching for the content directly, or vouching for the identity that submitted it.) Upvoting a piece of content vouches for it, and increases your identity's trust in the content's submitter. Flagging a piece of content distrusts it and decreases your identity's trust in the content's submitter (possibly by a large amount depending on the flag type), and in other identities that vouched for that content. Previously unseen identities are assigned a reputation based on how much other identities you trust (and they identities they trust, etc.) trust or distrust that unseen identity.
The advantage of this system is that it not only prevents sibyl attacks, but also doubles as a form of fully decentralized community-driven moderation.
That's the general idea anyway. The exact details of how a system like that would work probably need a lot of fleshing out and real-world testing in order to make them work effectively.