Hey,
Are you both on the same network by any chance? If you are, then try having whoever connects to the game servers first (whoever gets on the game first) to be the one who invites the other to join them.
I would also suggest you both go through the troubleshooting found here.