Unfortunately, the latest update did not fix whatever problem is plaguing us. Connecting to each other seems as random and sporadic as ever. We managed to connect after multiple tries and play for a while, but when a glitch occurred that necessitated restarting the game I was unable to rejoin after at least 30 tries.

We both tried verifying the integrity of game files. There were actually missing files that had to be redownloaded but this did not seem to affect our problem. I feel like port forwarding should not be necessary because it is going through Steam's matchmaking service and we are able to play with each other on all other Steam games just fine. We are both running Windows 7 and can play the game single player easily so it does not seem to be that type of issue.

The two of us both live in the United States.

We have tried it with the host in character creation and in the world. It has worked a couple of times in both places so that does not seem to be a factor.