I don't have Divinity yet (I got on this forum just to investigate how the co-op works before buying it), but I might be able to offer a little troubleshooting advice based on some prior experience.
The symptoms that are being described here are exactly what was happening to my son and I with Disney Infinity 2.0 and 3.0. Both of us had open NATs and we've had no problems connecting with each other or anyone else with any other game, yet we couldn't connect in Infinity. We tried port forwarding, putting either Xbox One in the DMZ, alternating who hosted and how/when we would send an invite, and we even bought a block of static IP addresses from our ISP (U-Verse). Nothing worked. Sounding familiar?
It turned out that the problem was with our U-Verse modem/router (Motorola/Arris NVG589). I believe Comcast uses this same unit for a number of customers. We tested this by using our neighbor's wi-fi signal on his router (this allowed us to connect in multiplayer). We also used our iPhones to set up mobile hotspots and connected wirelessly using those. Granted, neither of those are long term solutions, but it is a way that you can test to see if the problem is specific to your modem / router / residential gateway.
