Genuine encryption from only one source?
I think the solution to your problem is a digital signature as CodesInChaos pointed out. Here is how it would work:

When a user registers with your server they are given a token which will consist of (at a minimum) the user's id. The server also uses its private key to digitally sign the token (or more likely a hash of the token). 

Now, say user1 and user2 have done this and now want to communicate. They each send their token and digital signature to the other user. They each take the token and signature that they received from the other user, and use the servers public key to verify that the signature was correct. If so they proceed to communicate. 

There are some things you will want to think about before using this, however. You might want to kick people out of the network. That will require some additional work.