Did you get the game via Steam? There is a problem in that these users cannot play with people who bought the game in a shop.

Is it possible you are using a mod or have somehow changed the game's files?