1. Use a hashcash style proof of work mechanism to register account. The server send a challenge and have the client compute a nonce under the difficulty. This could be turned to take an average of seconds to minutes on your median users device.
This isn't a long term solution because eventually an attacker will realize that they can use more powerful machines to create sybils and abuse your network.
I'm actively working on alternatives ATM.
2. Embed Tor. The Guardian Project folks will be able to give advice on embedding a tor proxy in your app. There is documentation online as well. Chatsecure has done this.
This would reduce the amount of information you have in your possession for authorities to seize.
This would not protect your user base if authorities compel you to ship a malicious software update.
3. Also use SSL and pin your public key for your SSL cert