Did you check you firewall, anti-virus and router settings? Have you tried with any anti-virus or third party firewall software disabled, and all non-essential programs shut down?
Have you tried switching who was hosting?
Have you tried using Direct Connection, with an IP address or 'Server ID' (which the host can get after loading the game, in the Connection Menu [diamond icon on top of the mini-map])? You would need to use an IP address to join during character creation, so both people could customize their own character.
Can you try a LAN connection? If you are not on the same LAN, though, you would need to use VPN software like Hamachi or Tunngle.
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).
