Are you using a pirated version, or retail?
I know that with the pirated version you can only interact with people running servers that accept that.
I'm not sure if that helps any, just something I ran into awhile back.
Also, try checking for the latest patches, and make sure you are both running the same one.