My brother and I had the same problem, "Host NAT TBD" and not able to connect. In netstat I could see that the game would open a new UDP port every few seconds, but close it shortly after, and then start over doing the same thing. That made it impossible to port forward the ports, too. I've manually added the game to the Windows firewall as well (it never asked me for firewall permissions, so I had to add it manually).
We bought the game only for multiplayer and we're not able to play at all, which is very disappointing. It would be great to learn more about what else we can do to fix this.