I assume you both tried hosting? Have either of you played co-op with anyone else?
Did you both check your anti-virus or firewall settings, or (if applicable) try with them disabled?
For Direct Connection, did you try the Server ID, as well as by IP address?
The host can get the Server ID after loading the game, in the Connection Menu (the diamond icon on top of the mini-map).
It might help to enable port forwarding in your router(s). Copied from a forum topic;
The game's client will try to assign a port in the range 23243-23252, the server in the range 23253-23262. While forwarding these ports on your gateway might help, there is no guarantee the gateway will assign an external port in this range when connecting to our NATPunch server (this is the port that will be assumed to be the external port for all connections).
